/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_unwindbound100.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-05ce600 [2022-02-23 19:27:53,254 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-02-23 19:27:53,255 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-02-23 19:27:53,287 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-02-23 19:27:53,288 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-02-23 19:27:53,289 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-02-23 19:27:53,290 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-02-23 19:27:53,291 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-02-23 19:27:53,292 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-02-23 19:27:53,293 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-02-23 19:27:53,294 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-02-23 19:27:53,295 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-02-23 19:27:53,295 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-02-23 19:27:53,296 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-02-23 19:27:53,297 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-02-23 19:27:53,298 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-02-23 19:27:53,298 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-02-23 19:27:53,301 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-02-23 19:27:53,304 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-02-23 19:27:53,305 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-02-23 19:27:53,306 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-02-23 19:27:53,312 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-02-23 19:27:53,313 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-02-23 19:27:53,314 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-02-23 19:27:53,316 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-02-23 19:27:53,316 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-02-23 19:27:53,316 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-02-23 19:27:53,317 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-02-23 19:27:53,317 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-02-23 19:27:53,318 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-02-23 19:27:53,318 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-02-23 19:27:53,319 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-02-23 19:27:53,319 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-02-23 19:27:53,320 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-02-23 19:27:53,320 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-02-23 19:27:53,321 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-02-23 19:27:53,321 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-02-23 19:27:53,321 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-02-23 19:27:53,322 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-02-23 19:27:53,322 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-02-23 19:27:53,323 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-02-23 19:27:53,324 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/LoopAccelerationJordanC.epf [2022-02-23 19:27:53,331 INFO L113 SettingsManager]: Loading preferences was successful [2022-02-23 19:27:53,331 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-02-23 19:27:53,332 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-02-23 19:27:53,332 INFO L138 SettingsManager]: * sizeof long=4 [2022-02-23 19:27:53,332 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-02-23 19:27:53,332 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-02-23 19:27:53,332 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-02-23 19:27:53,332 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-02-23 19:27:53,332 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-02-23 19:27:53,333 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-02-23 19:27:53,333 INFO L138 SettingsManager]: * sizeof long double=12 [2022-02-23 19:27:53,333 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-02-23 19:27:53,333 INFO L138 SettingsManager]: * Use constant arrays=true [2022-02-23 19:27:53,333 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-02-23 19:27:53,333 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-02-23 19:27:53,333 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-02-23 19:27:53,333 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-02-23 19:27:53,334 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-02-23 19:27:53,334 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-02-23 19:27:53,334 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-02-23 19:27:53,334 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-02-23 19:27:53,334 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-02-23 19:27:53,335 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-02-23 19:27:53,517 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-02-23 19:27:53,539 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-02-23 19:27:53,541 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-02-23 19:27:53,542 INFO L271 PluginConnector]: Initializing CDTParser... [2022-02-23 19:27:53,543 INFO L275 PluginConnector]: CDTParser initialized [2022-02-23 19:27:53,544 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/ps4-ll_unwindbound100.c [2022-02-23 19:27:53,598 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/94aa060bd/3d18b87046d844c9a12c1a902db31754/FLAGd8829520d [2022-02-23 19:27:53,929 INFO L306 CDTParser]: Found 1 translation units. [2022-02-23 19:27:53,929 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/ps4-ll_unwindbound100.c [2022-02-23 19:27:53,933 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/94aa060bd/3d18b87046d844c9a12c1a902db31754/FLAGd8829520d [2022-02-23 19:27:53,942 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/94aa060bd/3d18b87046d844c9a12c1a902db31754 [2022-02-23 19:27:53,944 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-02-23 19:27:53,945 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-02-23 19:27:53,946 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-02-23 19:27:53,946 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-02-23 19:27:53,953 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-02-23 19:27:53,953 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.02 07:27:53" (1/1) ... [2022-02-23 19:27:53,954 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@65331908 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 07:27:53, skipping insertion in model container [2022-02-23 19:27:53,954 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.02 07:27:53" (1/1) ... [2022-02-23 19:27:53,960 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-02-23 19:27:53,971 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-02-23 19:27:54,111 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_unwindbound100.c[458,471] [2022-02-23 19:27:54,128 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-02-23 19:27:54,133 INFO L203 MainTranslator]: Completed pre-run [2022-02-23 19:27:54,140 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_unwindbound100.c[458,471] [2022-02-23 19:27:54,145 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-02-23 19:27:54,155 INFO L208 MainTranslator]: Completed translation [2022-02-23 19:27:54,156 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 07:27:54 WrapperNode [2022-02-23 19:27:54,156 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-02-23 19:27:54,157 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-02-23 19:27:54,157 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-02-23 19:27:54,157 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-02-23 19:27:54,164 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 07:27:54" (1/1) ... [2022-02-23 19:27:54,164 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 07:27:54" (1/1) ... [2022-02-23 19:27:54,168 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 07:27:54" (1/1) ... [2022-02-23 19:27:54,168 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 07:27:54" (1/1) ... [2022-02-23 19:27:54,171 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 07:27:54" (1/1) ... [2022-02-23 19:27:54,174 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 07:27:54" (1/1) ... [2022-02-23 19:27:54,175 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 07:27:54" (1/1) ... [2022-02-23 19:27:54,176 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-02-23 19:27:54,177 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-02-23 19:27:54,177 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-02-23 19:27:54,177 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-02-23 19:27:54,178 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 07:27:54" (1/1) ... [2022-02-23 19:27:54,184 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-02-23 19:27:54,194 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 19:27:54,208 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-02-23 19:27:54,223 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-02-23 19:27:54,250 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-02-23 19:27:54,250 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-02-23 19:27:54,250 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-02-23 19:27:54,250 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-02-23 19:27:54,250 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-02-23 19:27:54,250 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-02-23 19:27:54,251 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-02-23 19:27:54,251 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-02-23 19:27:54,251 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-02-23 19:27:54,251 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-02-23 19:27:54,251 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_short [2022-02-23 19:27:54,251 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-02-23 19:27:54,251 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-02-23 19:27:54,251 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-02-23 19:27:54,252 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-02-23 19:27:54,252 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-02-23 19:27:54,252 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-02-23 19:27:54,252 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-02-23 19:27:54,252 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-02-23 19:27:54,252 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-02-23 19:27:54,301 INFO L234 CfgBuilder]: Building ICFG [2022-02-23 19:27:54,302 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-02-23 19:27:54,394 INFO L275 CfgBuilder]: Performing block encoding [2022-02-23 19:27:54,398 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-02-23 19:27:54,399 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-02-23 19:27:54,400 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.02 07:27:54 BoogieIcfgContainer [2022-02-23 19:27:54,400 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-02-23 19:27:54,401 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-02-23 19:27:54,401 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-02-23 19:27:54,402 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-02-23 19:27:54,405 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.02 07:27:54" (1/1) ... [2022-02-23 19:27:54,420 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 23.02 07:27:54 BasicIcfg [2022-02-23 19:27:54,420 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-02-23 19:27:54,422 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-02-23 19:27:54,422 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-02-23 19:27:54,424 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-02-23 19:27:54,424 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 23.02 07:27:53" (1/4) ... [2022-02-23 19:27:54,425 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@68a7826c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.02 07:27:54, skipping insertion in model container [2022-02-23 19:27:54,425 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 07:27:54" (2/4) ... [2022-02-23 19:27:54,425 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@68a7826c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.02 07:27:54, skipping insertion in model container [2022-02-23 19:27:54,426 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.02 07:27:54" (3/4) ... [2022-02-23 19:27:54,426 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@68a7826c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 23.02 07:27:54, skipping insertion in model container [2022-02-23 19:27:54,426 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 23.02 07:27:54" (4/4) ... [2022-02-23 19:27:54,427 INFO L111 eAbstractionObserver]: Analyzing ICFG ps4-ll_unwindbound100.cJordan [2022-02-23 19:27:54,435 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:ForwardPredicates Determinization: PREDICATE_ABSTRACTION [2022-02-23 19:27:54,435 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-02-23 19:27:54,496 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-02-23 19:27:54,502 INFO L339 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, mLoopAccelerationTechnique=FAST_UPR [2022-02-23 19:27:54,502 INFO L340 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-02-23 19:27:54,513 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-02-23 19:27:54,519 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2022-02-23 19:27:54,520 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 19:27:54,520 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 19:27:54,521 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 19:27:54,525 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 19:27:54,525 INFO L85 PathProgramCache]: Analyzing trace with hash 1984627219, now seen corresponding path program 1 times [2022-02-23 19:27:54,533 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 19:27:54,533 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [981841010] [2022-02-23 19:27:54,533 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 19:27:54,534 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 19:27:54,609 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 19:27:54,697 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-02-23 19:27:54,700 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 19:27:54,712 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-02-23 19:27:54,712 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 19:27:54,713 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [981841010] [2022-02-23 19:27:54,713 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [981841010] provided 1 perfect and 0 imperfect interpolant sequences [2022-02-23 19:27:54,713 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-02-23 19:27:54,714 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-02-23 19:27:54,715 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [638771323] [2022-02-23 19:27:54,716 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-23 19:27:54,719 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-02-23 19:27:54,719 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 19:27:54,750 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-02-23 19:27:54,752 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-02-23 19:27:54,754 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-02-23 19:27:54,814 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 19:27:54,815 INFO L93 Difference]: Finished difference Result 24 states and 27 transitions. [2022-02-23 19:27:54,816 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-02-23 19:27:54,817 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-02-23 19:27:54,817 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 19:27:54,825 INFO L225 Difference]: With dead ends: 24 [2022-02-23 19:27:54,826 INFO L226 Difference]: Without dead ends: 19 [2022-02-23 19:27:54,827 INFO L932 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-02-23 19:27:54,834 INFO L933 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-02-23 19:27:54,836 INFO L934 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-02-23 19:27:54,851 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states. [2022-02-23 19:27:54,872 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 18. [2022-02-23 19:27:54,873 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-02-23 19:27:54,874 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 18 states to 18 states and 21 transitions. [2022-02-23 19:27:54,875 INFO L78 Accepts]: Start accepts. Automaton has 18 states and 21 transitions. Word has length 11 [2022-02-23 19:27:54,875 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 19:27:54,876 INFO L470 AbstractCegarLoop]: Abstraction has 18 states and 21 transitions. [2022-02-23 19:27:54,876 INFO L471 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-02-23 19:27:54,876 INFO L276 IsEmpty]: Start isEmpty. Operand 18 states and 21 transitions. [2022-02-23 19:27:54,877 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-02-23 19:27:54,877 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 19:27:54,877 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 19:27:54,878 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-02-23 19:27:54,878 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 19:27:54,884 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 19:27:54,884 INFO L85 PathProgramCache]: Analyzing trace with hash 1423332195, now seen corresponding path program 1 times [2022-02-23 19:27:54,884 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 19:27:54,885 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1566041874] [2022-02-23 19:27:54,885 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 19:27:54,885 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 19:27:54,906 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 19:27:54,906 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [391307739] [2022-02-23 19:27:54,906 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 19:27:54,907 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 19:27:54,907 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 19:27:54,913 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-02-23 19:27:54,914 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-02-23 19:27:54,978 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 19:27:54,980 INFO L263 TraceCheckSpWp]: Trace formula consists of 71 conjuncts, 5 conjunts are in the unsatisfiable core [2022-02-23 19:27:54,984 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 19:27:55,057 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-02-23 19:27:55,057 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-02-23 19:27:55,057 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 19:27:55,057 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1566041874] [2022-02-23 19:27:55,058 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 19:27:55,058 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [391307739] [2022-02-23 19:27:55,058 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [391307739] provided 1 perfect and 0 imperfect interpolant sequences [2022-02-23 19:27:55,058 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-02-23 19:27:55,058 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-02-23 19:27:55,059 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1781539756] [2022-02-23 19:27:55,059 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-23 19:27:55,060 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-02-23 19:27:55,060 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 19:27:55,061 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-02-23 19:27:55,061 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-02-23 19:27:55,061 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-02-23 19:27:55,071 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 19:27:55,071 INFO L93 Difference]: Finished difference Result 20 states and 23 transitions. [2022-02-23 19:27:55,071 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-02-23 19:27:55,071 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-02-23 19:27:55,072 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 19:27:55,072 INFO L225 Difference]: With dead ends: 20 [2022-02-23 19:27:55,072 INFO L226 Difference]: Without dead ends: 20 [2022-02-23 19:27:55,073 INFO L932 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-02-23 19:27:55,074 INFO L933 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-02-23 19:27:55,074 INFO L934 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-02-23 19:27:55,075 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2022-02-23 19:27:55,077 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 20. [2022-02-23 19:27:55,077 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-02-23 19:27:55,078 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 23 transitions. [2022-02-23 19:27:55,078 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 23 transitions. Word has length 12 [2022-02-23 19:27:55,079 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 19:27:55,079 INFO L470 AbstractCegarLoop]: Abstraction has 20 states and 23 transitions. [2022-02-23 19:27:55,079 INFO L471 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-02-23 19:27:55,079 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 23 transitions. [2022-02-23 19:27:55,079 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-02-23 19:27:55,080 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 19:27:55,080 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 19:27:55,105 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-02-23 19:27:55,302 WARN L452 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-02-23 19:27:55,303 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 19:27:55,303 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 19:27:55,303 INFO L85 PathProgramCache]: Analyzing trace with hash 1424404671, now seen corresponding path program 1 times [2022-02-23 19:27:55,304 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 19:27:55,304 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1164849904] [2022-02-23 19:27:55,304 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 19:27:55,304 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 19:27:55,315 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 19:27:55,315 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [722526434] [2022-02-23 19:27:55,315 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 19:27:55,315 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 19:27:55,315 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 19:27:55,324 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-02-23 19:27:55,328 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-02-23 19:27:55,369 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 19:27:55,370 INFO L263 TraceCheckSpWp]: Trace formula consists of 71 conjuncts, 7 conjunts are in the unsatisfiable core [2022-02-23 19:27:55,372 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 19:27:55,452 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-02-23 19:27:55,452 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-02-23 19:27:55,452 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 19:27:55,452 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1164849904] [2022-02-23 19:27:55,452 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 19:27:55,453 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [722526434] [2022-02-23 19:27:55,453 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [722526434] provided 1 perfect and 0 imperfect interpolant sequences [2022-02-23 19:27:55,453 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-02-23 19:27:55,453 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-02-23 19:27:55,453 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1981016841] [2022-02-23 19:27:55,454 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-23 19:27:55,454 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-02-23 19:27:55,454 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 19:27:55,455 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-02-23 19:27:55,455 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-02-23 19:27:55,455 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-02-23 19:27:55,486 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 19:27:55,486 INFO L93 Difference]: Finished difference Result 28 states and 33 transitions. [2022-02-23 19:27:55,486 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-02-23 19:27:55,486 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-02-23 19:27:55,487 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 19:27:55,487 INFO L225 Difference]: With dead ends: 28 [2022-02-23 19:27:55,487 INFO L226 Difference]: Without dead ends: 26 [2022-02-23 19:27:55,488 INFO L932 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-02-23 19:27:55,489 INFO L933 BasicCegarLoop]: 19 mSDtfsCounter, 6 mSDsluCounter, 52 mSDsCounter, 0 mSdLazyCounter, 21 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 71 SdHoareTripleChecker+Invalid, 23 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 21 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-02-23 19:27:55,489 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 71 Invalid, 23 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 21 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-02-23 19:27:55,490 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2022-02-23 19:27:55,501 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2022-02-23 19:27:55,501 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-02-23 19:27:55,502 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 29 transitions. [2022-02-23 19:27:55,502 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 29 transitions. Word has length 12 [2022-02-23 19:27:55,502 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 19:27:55,503 INFO L470 AbstractCegarLoop]: Abstraction has 26 states and 29 transitions. [2022-02-23 19:27:55,503 INFO L471 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-02-23 19:27:55,503 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 29 transitions. [2022-02-23 19:27:55,503 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2022-02-23 19:27:55,504 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 19:27:55,504 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 19:27:55,530 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-02-23 19:27:55,729 WARN L452 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-02-23 19:27:55,730 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 19:27:55,731 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 19:27:55,731 INFO L85 PathProgramCache]: Analyzing trace with hash -381498108, now seen corresponding path program 1 times [2022-02-23 19:27:55,731 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 19:27:55,731 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1133723053] [2022-02-23 19:27:55,731 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 19:27:55,732 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 19:27:55,744 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 19:27:55,744 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [828675629] [2022-02-23 19:27:55,744 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 19:27:55,744 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 19:27:55,744 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 19:27:55,752 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-02-23 19:27:55,754 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-02-23 19:27:55,811 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 19:27:55,812 INFO L263 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 7 conjunts are in the unsatisfiable core [2022-02-23 19:27:55,814 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 19:27:55,875 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-02-23 19:27:55,875 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 19:27:55,945 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-02-23 19:27:55,945 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 19:27:55,945 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1133723053] [2022-02-23 19:27:55,945 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 19:27:55,946 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [828675629] [2022-02-23 19:27:55,946 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [828675629] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-23 19:27:55,946 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-23 19:27:55,946 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2022-02-23 19:27:55,946 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1061668854] [2022-02-23 19:27:55,946 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-23 19:27:55,947 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-02-23 19:27:55,947 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 19:27:55,948 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-02-23 19:27:55,948 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2022-02-23 19:27:55,948 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-02-23 19:27:56,019 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 19:27:56,019 INFO L93 Difference]: Finished difference Result 52 states and 59 transitions. [2022-02-23 19:27:56,020 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-02-23 19:27:56,020 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-02-23 19:27:56,020 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 19:27:56,021 INFO L225 Difference]: With dead ends: 52 [2022-02-23 19:27:56,021 INFO L226 Difference]: Without dead ends: 52 [2022-02-23 19:27:56,022 INFO L932 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-02-23 19:27:56,023 INFO L933 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.0s IncrementalHoareTripleChecker+Time [2022-02-23 19:27:56,023 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [39 Valid, 86 Invalid, 51 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 34 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-02-23 19:27:56,024 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2022-02-23 19:27:56,030 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 48. [2022-02-23 19:27:56,030 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-02-23 19:27:56,031 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 57 transitions. [2022-02-23 19:27:56,032 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 57 transitions. Word has length 20 [2022-02-23 19:27:56,032 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 19:27:56,032 INFO L470 AbstractCegarLoop]: Abstraction has 48 states and 57 transitions. [2022-02-23 19:27:56,032 INFO L471 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-02-23 19:27:56,032 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 57 transitions. [2022-02-23 19:27:56,033 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2022-02-23 19:27:56,033 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 19:27:56,033 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 19:27:56,050 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2022-02-23 19:27:56,239 WARN L452 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-02-23 19:27:56,240 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 19:27:56,240 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 19:27:56,240 INFO L85 PathProgramCache]: Analyzing trace with hash -380425632, now seen corresponding path program 1 times [2022-02-23 19:27:56,241 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 19:27:56,241 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [275255656] [2022-02-23 19:27:56,241 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 19:27:56,241 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 19:27:56,249 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 19:27:56,250 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1416393599] [2022-02-23 19:27:56,250 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 19:27:56,250 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 19:27:56,250 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 19:27:56,251 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-02-23 19:27:56,256 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-02-23 19:27:56,290 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 19:27:56,291 INFO L263 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 11 conjunts are in the unsatisfiable core [2022-02-23 19:27:56,293 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 19:27:56,413 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-02-23 19:27:56,413 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 19:27:56,582 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-02-23 19:27:56,583 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 19:27:56,583 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [275255656] [2022-02-23 19:27:56,583 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 19:27:56,583 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1416393599] [2022-02-23 19:27:56,583 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1416393599] provided 1 perfect and 1 imperfect interpolant sequences [2022-02-23 19:27:56,583 INFO L191 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-02-23 19:27:56,583 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2022-02-23 19:27:56,584 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [66740680] [2022-02-23 19:27:56,584 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-23 19:27:56,584 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-02-23 19:27:56,584 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 19:27:56,585 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-02-23 19:27:56,585 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-02-23 19:27:56,585 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-02-23 19:27:56,613 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 19:27:56,613 INFO L93 Difference]: Finished difference Result 60 states and 66 transitions. [2022-02-23 19:27:56,614 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-02-23 19:27:56,614 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-02-23 19:27:56,614 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 19:27:56,615 INFO L225 Difference]: With dead ends: 60 [2022-02-23 19:27:56,615 INFO L226 Difference]: Without dead ends: 51 [2022-02-23 19:27:56,615 INFO L932 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-02-23 19:27:56,616 INFO L933 BasicCegarLoop]: 17 mSDtfsCounter, 7 mSDsluCounter, 42 mSDsCounter, 0 mSdLazyCounter, 15 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 59 SdHoareTripleChecker+Invalid, 16 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 15 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-02-23 19:27:56,616 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 59 Invalid, 16 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 15 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-02-23 19:27:56,617 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2022-02-23 19:27:56,621 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 45. [2022-02-23 19:27:56,621 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-02-23 19:27:56,622 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 48 transitions. [2022-02-23 19:27:56,622 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 48 transitions. Word has length 20 [2022-02-23 19:27:56,622 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 19:27:56,622 INFO L470 AbstractCegarLoop]: Abstraction has 45 states and 48 transitions. [2022-02-23 19:27:56,622 INFO L471 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-02-23 19:27:56,623 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 48 transitions. [2022-02-23 19:27:56,623 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2022-02-23 19:27:56,623 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 19:27:56,623 INFO L514 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 19:27:56,649 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2022-02-23 19:27:56,843 WARN L452 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-02-23 19:27:56,844 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 19:27:56,844 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 19:27:56,844 INFO L85 PathProgramCache]: Analyzing trace with hash 1647871298, now seen corresponding path program 1 times [2022-02-23 19:27:56,844 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 19:27:56,844 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [111392352] [2022-02-23 19:27:56,845 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 19:27:56,845 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 19:27:56,853 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 19:27:56,854 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [949836105] [2022-02-23 19:27:56,854 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 19:27:56,854 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 19:27:56,854 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 19:27:56,859 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-02-23 19:27:56,860 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-02-23 19:27:56,898 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 19:27:56,899 INFO L263 TraceCheckSpWp]: Trace formula consists of 102 conjuncts, 19 conjunts are in the unsatisfiable core [2022-02-23 19:27:56,901 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 19:27:57,157 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 6 proven. 5 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-02-23 19:27:57,157 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 19:28:01,399 WARN L838 $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 (<= (div (+ .cse0 .cse1 4 .cse2) 4) (+ (* 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))))) (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-02-23 19:28:03,479 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 19:28:03,480 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [111392352] [2022-02-23 19:28:03,480 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 19:28:03,480 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [949836105] [2022-02-23 19:28:03,480 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [949836105] provided 0 perfect and 1 imperfect interpolant sequences [2022-02-23 19:28:03,480 INFO L191 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-02-23 19:28:03,480 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2022-02-23 19:28:03,480 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [794646043] [2022-02-23 19:28:03,481 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-02-23 19:28:03,481 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-02-23 19:28:03,481 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 19:28:03,481 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-02-23 19:28:03,482 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=140, Unknown=1, NotChecked=24, Total=210 [2022-02-23 19:28:03,482 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-02-23 19:28:03,582 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 19:28:03,582 INFO L93 Difference]: Finished difference Result 48 states and 50 transitions. [2022-02-23 19:28:03,584 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-02-23 19:28:03,584 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-02-23 19:28:03,584 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 19:28:03,584 INFO L225 Difference]: With dead ends: 48 [2022-02-23 19:28:03,585 INFO L226 Difference]: Without dead ends: 45 [2022-02-23 19:28:03,585 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 25 SyntacticMatches, 1 SemanticMatches, 16 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 19 ImplicationChecksByTransitivity, 2.2s TimeCoverageRelationStatistics Valid=66, Invalid=209, Unknown=1, NotChecked=30, Total=306 [2022-02-23 19:28:03,586 INFO L933 BasicCegarLoop]: 17 mSDtfsCounter, 9 mSDsluCounter, 96 mSDsCounter, 0 mSdLazyCounter, 76 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 113 SdHoareTripleChecker+Invalid, 78 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 76 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-02-23 19:28:03,586 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 113 Invalid, 78 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 76 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-02-23 19:28:03,586 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2022-02-23 19:28:03,589 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 45. [2022-02-23 19:28:03,589 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-02-23 19:28:03,590 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 47 transitions. [2022-02-23 19:28:03,592 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 47 transitions. Word has length 26 [2022-02-23 19:28:03,593 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 19:28:03,593 INFO L470 AbstractCegarLoop]: Abstraction has 45 states and 47 transitions. [2022-02-23 19:28:03,593 INFO L471 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-02-23 19:28:03,593 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 47 transitions. [2022-02-23 19:28:03,593 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2022-02-23 19:28:03,594 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 19:28:03,594 INFO L514 BasicCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 19:28:03,618 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-02-23 19:28:03,794 WARN L452 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-02-23 19:28:03,794 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 19:28:03,795 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 19:28:03,795 INFO L85 PathProgramCache]: Analyzing trace with hash 31133987, now seen corresponding path program 2 times [2022-02-23 19:28:03,795 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 19:28:03,795 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1945687906] [2022-02-23 19:28:03,795 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 19:28:03,795 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 19:28:03,806 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 19:28:03,806 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [178888367] [2022-02-23 19:28:03,806 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-02-23 19:28:03,807 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 19:28:03,807 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 19:28:03,808 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-02-23 19:28:03,809 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-02-23 19:28:03,854 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-02-23 19:28:03,854 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-02-23 19:28:03,855 INFO L263 TraceCheckSpWp]: Trace formula consists of 123 conjuncts, 16 conjunts are in the unsatisfiable core [2022-02-23 19:28:03,857 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 19:28:04,033 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 6 proven. 12 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-02-23 19:28:04,034 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 19:28:04,218 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 19:28:04,218 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1945687906] [2022-02-23 19:28:04,218 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 19:28:04,218 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [178888367] [2022-02-23 19:28:04,219 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [178888367] provided 0 perfect and 1 imperfect interpolant sequences [2022-02-23 19:28:04,219 INFO L191 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-02-23 19:28:04,219 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2022-02-23 19:28:04,219 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [807712205] [2022-02-23 19:28:04,219 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-02-23 19:28:04,219 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-02-23 19:28:04,219 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 19:28:04,220 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-02-23 19:28:04,220 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2022-02-23 19:28:04,220 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-02-23 19:28:04,279 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 19:28:04,279 INFO L93 Difference]: Finished difference Result 48 states and 49 transitions. [2022-02-23 19:28:04,279 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-02-23 19:28:04,280 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-02-23 19:28:04,280 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 19:28:04,280 INFO L225 Difference]: With dead ends: 48 [2022-02-23 19:28:04,280 INFO L226 Difference]: Without dead ends: 45 [2022-02-23 19:28:04,281 INFO L932 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-02-23 19:28:04,281 INFO L933 BasicCegarLoop]: 26 mSDtfsCounter, 2 mSDsluCounter, 126 mSDsCounter, 0 mSdLazyCounter, 51 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 152 SdHoareTripleChecker+Invalid, 51 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 51 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-02-23 19:28:04,281 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 152 Invalid, 51 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 51 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-02-23 19:28:04,282 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2022-02-23 19:28:04,285 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 45. [2022-02-23 19:28:04,285 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-02-23 19:28:04,285 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 46 transitions. [2022-02-23 19:28:04,286 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 46 transitions. Word has length 34 [2022-02-23 19:28:04,286 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 19:28:04,286 INFO L470 AbstractCegarLoop]: Abstraction has 45 states and 46 transitions. [2022-02-23 19:28:04,286 INFO L471 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-02-23 19:28:04,286 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 46 transitions. [2022-02-23 19:28:04,287 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2022-02-23 19:28:04,287 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 19:28:04,287 INFO L514 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 19:28:04,312 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-02-23 19:28:04,507 WARN L452 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-02-23 19:28:04,508 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 19:28:04,508 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 19:28:04,508 INFO L85 PathProgramCache]: Analyzing trace with hash 1474833412, now seen corresponding path program 3 times [2022-02-23 19:28:04,508 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 19:28:04,508 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [426519753] [2022-02-23 19:28:04,508 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 19:28:04,508 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 19:28:04,516 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 19:28:04,516 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1079932172] [2022-02-23 19:28:04,516 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-02-23 19:28:04,516 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 19:28:04,516 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 19:28:04,520 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-02-23 19:28:04,522 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-02-23 19:28:04,601 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2022-02-23 19:28:04,601 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-02-23 19:28:04,602 INFO L263 TraceCheckSpWp]: Trace formula consists of 144 conjuncts, 20 conjunts are in the unsatisfiable core [2022-02-23 19:28:04,604 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 19:28:04,807 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 8 proven. 24 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-02-23 19:28:04,807 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 19:28:04,939 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 19:28:04,939 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [426519753] [2022-02-23 19:28:04,940 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 19:28:04,940 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1079932172] [2022-02-23 19:28:04,940 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1079932172] provided 0 perfect and 1 imperfect interpolant sequences [2022-02-23 19:28:04,940 INFO L191 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-02-23 19:28:04,940 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2022-02-23 19:28:04,940 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1393362268] [2022-02-23 19:28:04,940 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-02-23 19:28:04,940 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-02-23 19:28:04,940 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 19:28:04,941 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-02-23 19:28:04,941 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2022-02-23 19:28:04,941 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-02-23 19:28:05,026 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 19:28:05,026 INFO L93 Difference]: Finished difference Result 50 states and 52 transitions. [2022-02-23 19:28:05,027 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-02-23 19:28:05,027 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-02-23 19:28:05,027 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 19:28:05,027 INFO L225 Difference]: With dead ends: 50 [2022-02-23 19:28:05,028 INFO L226 Difference]: Without dead ends: 47 [2022-02-23 19:28:05,028 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 44 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=40, Invalid=142, Unknown=0, NotChecked=0, Total=182 [2022-02-23 19:28:05,028 INFO L933 BasicCegarLoop]: 30 mSDtfsCounter, 2 mSDsluCounter, 168 mSDsCounter, 0 mSdLazyCounter, 72 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 198 SdHoareTripleChecker+Invalid, 72 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 72 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-02-23 19:28:05,029 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 198 Invalid, 72 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 72 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-02-23 19:28:05,029 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2022-02-23 19:28:05,032 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 47. [2022-02-23 19:28:05,032 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-02-23 19:28:05,033 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 49 transitions. [2022-02-23 19:28:05,033 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 49 transitions. Word has length 42 [2022-02-23 19:28:05,033 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 19:28:05,033 INFO L470 AbstractCegarLoop]: Abstraction has 47 states and 49 transitions. [2022-02-23 19:28:05,033 INFO L471 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-02-23 19:28:05,033 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 49 transitions. [2022-02-23 19:28:05,034 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2022-02-23 19:28:05,034 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 19:28:05,034 INFO L514 BasicCegarLoop]: trace histogram [5, 5, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 19:28:05,056 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-02-23 19:28:05,235 WARN L452 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-02-23 19:28:05,235 INFO L402 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 19:28:05,236 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 19:28:05,236 INFO L85 PathProgramCache]: Analyzing trace with hash 831591399, now seen corresponding path program 2 times [2022-02-23 19:28:05,236 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 19:28:05,236 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [109345513] [2022-02-23 19:28:05,236 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 19:28:05,236 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 19:28:05,244 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 19:28:05,244 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [832096120] [2022-02-23 19:28:05,244 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-02-23 19:28:05,244 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 19:28:05,244 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 19:28:05,245 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-02-23 19:28:05,246 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-02-23 19:28:05,297 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-02-23 19:28:05,297 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-02-23 19:28:05,298 INFO L263 TraceCheckSpWp]: Trace formula consists of 155 conjuncts, 13 conjunts are in the unsatisfiable core [2022-02-23 19:28:05,300 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 19:28:05,432 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 8 proven. 56 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-02-23 19:28:05,433 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 19:28:05,602 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 8 proven. 32 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-02-23 19:28:05,602 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 19:28:05,602 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [109345513] [2022-02-23 19:28:05,602 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 19:28:05,602 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [832096120] [2022-02-23 19:28:05,602 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [832096120] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-23 19:28:05,602 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-23 19:28:05,602 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2022-02-23 19:28:05,603 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [811897653] [2022-02-23 19:28:05,603 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-23 19:28:05,604 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-02-23 19:28:05,604 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 19:28:05,605 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-02-23 19:28:05,605 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2022-02-23 19:28:05,605 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-02-23 19:28:05,764 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 19:28:05,764 INFO L93 Difference]: Finished difference Result 118 states and 119 transitions. [2022-02-23 19:28:05,765 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2022-02-23 19:28:05,765 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-02-23 19:28:05,765 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 19:28:05,766 INFO L225 Difference]: With dead ends: 118 [2022-02-23 19:28:05,766 INFO L226 Difference]: Without dead ends: 118 [2022-02-23 19:28:05,767 INFO L932 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-02-23 19:28:05,767 INFO L933 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-02-23 19:28:05,767 INFO L934 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-02-23 19:28:05,768 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 118 states. [2022-02-23 19:28:05,773 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 118 to 93. [2022-02-23 19:28:05,773 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-02-23 19:28:05,774 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 99 transitions. [2022-02-23 19:28:05,774 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 99 transitions. Word has length 44 [2022-02-23 19:28:05,774 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 19:28:05,774 INFO L470 AbstractCegarLoop]: Abstraction has 93 states and 99 transitions. [2022-02-23 19:28:05,775 INFO L471 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-02-23 19:28:05,775 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 99 transitions. [2022-02-23 19:28:05,775 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2022-02-23 19:28:05,775 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 19:28:05,776 INFO L514 BasicCegarLoop]: trace histogram [6, 5, 5, 5, 5, 5, 5, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 19:28:05,801 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-02-23 19:28:05,998 WARN L452 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-02-23 19:28:05,998 INFO L402 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 19:28:05,999 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 19:28:05,999 INFO L85 PathProgramCache]: Analyzing trace with hash -1805593115, now seen corresponding path program 4 times [2022-02-23 19:28:05,999 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 19:28:05,999 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [534137762] [2022-02-23 19:28:05,999 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 19:28:05,999 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 19:28:06,007 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 19:28:06,007 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [412115537] [2022-02-23 19:28:06,007 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-02-23 19:28:06,007 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 19:28:06,007 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 19:28:06,011 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-02-23 19:28:06,012 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-02-23 19:28:06,090 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-02-23 19:28:06,090 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-02-23 19:28:06,091 INFO L263 TraceCheckSpWp]: Trace formula consists of 165 conjuncts, 24 conjunts are in the unsatisfiable core [2022-02-23 19:28:06,093 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 19:28:06,323 INFO L134 CoverageAnalysis]: Checked inductivity of 90 backedges. 10 proven. 40 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-02-23 19:28:06,323 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 19:28:06,446 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 19:28:06,446 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [534137762] [2022-02-23 19:28:06,447 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 19:28:06,447 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [412115537] [2022-02-23 19:28:06,447 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [412115537] provided 0 perfect and 1 imperfect interpolant sequences [2022-02-23 19:28:06,447 INFO L191 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-02-23 19:28:06,447 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2022-02-23 19:28:06,447 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1457064242] [2022-02-23 19:28:06,447 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-02-23 19:28:06,448 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-02-23 19:28:06,448 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 19:28:06,448 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-02-23 19:28:06,448 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=123, Unknown=0, NotChecked=0, Total=156 [2022-02-23 19:28:06,448 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-02-23 19:28:06,533 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 19:28:06,534 INFO L93 Difference]: Finished difference Result 96 states and 101 transitions. [2022-02-23 19:28:06,534 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-02-23 19:28:06,534 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-02-23 19:28:06,534 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 19:28:06,536 INFO L225 Difference]: With dead ends: 96 [2022-02-23 19:28:06,536 INFO L226 Difference]: Without dead ends: 93 [2022-02-23 19:28:06,536 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 51 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=43, Invalid=167, Unknown=0, NotChecked=0, Total=210 [2022-02-23 19:28:06,536 INFO L933 BasicCegarLoop]: 34 mSDtfsCounter, 2 mSDsluCounter, 216 mSDsCounter, 0 mSdLazyCounter, 97 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 250 SdHoareTripleChecker+Invalid, 97 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 97 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-02-23 19:28:06,537 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 250 Invalid, 97 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 97 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-02-23 19:28:06,537 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2022-02-23 19:28:06,542 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 93. [2022-02-23 19:28:06,542 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-02-23 19:28:06,543 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 98 transitions. [2022-02-23 19:28:06,543 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 98 transitions. Word has length 50 [2022-02-23 19:28:06,543 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 19:28:06,543 INFO L470 AbstractCegarLoop]: Abstraction has 93 states and 98 transitions. [2022-02-23 19:28:06,543 INFO L471 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-02-23 19:28:06,543 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 98 transitions. [2022-02-23 19:28:06,544 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2022-02-23 19:28:06,544 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 19:28:06,544 INFO L514 BasicCegarLoop]: trace histogram [7, 6, 6, 6, 6, 6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 19:28:06,567 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2022-02-23 19:28:06,766 WARN L452 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-02-23 19:28:06,767 INFO L402 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 19:28:06,767 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 19:28:06,767 INFO L85 PathProgramCache]: Analyzing trace with hash 1447431878, now seen corresponding path program 5 times [2022-02-23 19:28:06,767 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 19:28:06,767 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [616366268] [2022-02-23 19:28:06,767 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 19:28:06,767 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 19:28:06,775 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 19:28:06,775 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [115259788] [2022-02-23 19:28:06,775 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-02-23 19:28:06,775 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 19:28:06,776 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 19:28:06,777 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-02-23 19:28:06,778 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-02-23 19:28:06,963 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2022-02-23 19:28:06,964 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-02-23 19:28:06,965 INFO L263 TraceCheckSpWp]: Trace formula consists of 186 conjuncts, 28 conjunts are in the unsatisfiable core [2022-02-23 19:28:06,967 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 19:28:07,234 INFO L134 CoverageAnalysis]: Checked inductivity of 132 backedges. 12 proven. 60 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-02-23 19:28:07,234 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 19:28:07,365 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 19:28:07,365 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [616366268] [2022-02-23 19:28:07,365 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 19:28:07,366 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [115259788] [2022-02-23 19:28:07,366 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [115259788] provided 0 perfect and 1 imperfect interpolant sequences [2022-02-23 19:28:07,366 INFO L191 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-02-23 19:28:07,366 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2022-02-23 19:28:07,366 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [11984899] [2022-02-23 19:28:07,366 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-02-23 19:28:07,366 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-02-23 19:28:07,367 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 19:28:07,367 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-02-23 19:28:07,367 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=146, Unknown=0, NotChecked=0, Total=182 [2022-02-23 19:28:07,367 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-02-23 19:28:07,476 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 19:28:07,476 INFO L93 Difference]: Finished difference Result 96 states and 100 transitions. [2022-02-23 19:28:07,476 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-02-23 19:28:07,476 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-02-23 19:28:07,477 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 19:28:07,477 INFO L225 Difference]: With dead ends: 96 [2022-02-23 19:28:07,477 INFO L226 Difference]: Without dead ends: 93 [2022-02-23 19:28:07,478 INFO L932 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-02-23 19:28:07,478 INFO L933 BasicCegarLoop]: 38 mSDtfsCounter, 2 mSDsluCounter, 270 mSDsCounter, 0 mSdLazyCounter, 126 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 308 SdHoareTripleChecker+Invalid, 126 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 126 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-02-23 19:28:07,478 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 308 Invalid, 126 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 126 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-02-23 19:28:07,479 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2022-02-23 19:28:07,482 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 93. [2022-02-23 19:28:07,482 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-02-23 19:28:07,483 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 97 transitions. [2022-02-23 19:28:07,483 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 97 transitions. Word has length 58 [2022-02-23 19:28:07,483 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 19:28:07,483 INFO L470 AbstractCegarLoop]: Abstraction has 93 states and 97 transitions. [2022-02-23 19:28:07,484 INFO L471 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-02-23 19:28:07,484 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 97 transitions. [2022-02-23 19:28:07,484 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 67 [2022-02-23 19:28:07,484 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 19:28:07,484 INFO L514 BasicCegarLoop]: trace histogram [8, 7, 7, 7, 7, 7, 7, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 19:28:07,492 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-02-23 19:28:07,685 WARN L452 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-02-23 19:28:07,685 INFO L402 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 19:28:07,685 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 19:28:07,686 INFO L85 PathProgramCache]: Analyzing trace with hash -1416046937, now seen corresponding path program 6 times [2022-02-23 19:28:07,686 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 19:28:07,686 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1970306840] [2022-02-23 19:28:07,686 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 19:28:07,686 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 19:28:07,696 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 19:28:07,696 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2069389286] [2022-02-23 19:28:07,696 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-02-23 19:28:07,696 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 19:28:07,696 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 19:28:07,698 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-02-23 19:28:07,703 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-02-23 19:28:08,035 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2022-02-23 19:28:08,036 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-02-23 19:28:08,037 INFO L263 TraceCheckSpWp]: Trace formula consists of 207 conjuncts, 32 conjunts are in the unsatisfiable core [2022-02-23 19:28:08,039 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 19:28:08,313 INFO L134 CoverageAnalysis]: Checked inductivity of 182 backedges. 14 proven. 84 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2022-02-23 19:28:08,313 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 19:28:08,440 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 19:28:08,441 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1970306840] [2022-02-23 19:28:08,441 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 19:28:08,441 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2069389286] [2022-02-23 19:28:08,441 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2069389286] provided 0 perfect and 1 imperfect interpolant sequences [2022-02-23 19:28:08,441 INFO L191 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-02-23 19:28:08,441 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2022-02-23 19:28:08,441 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [293561033] [2022-02-23 19:28:08,441 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-02-23 19:28:08,442 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-02-23 19:28:08,442 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 19:28:08,442 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-02-23 19:28:08,442 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=171, Unknown=0, NotChecked=0, Total=210 [2022-02-23 19:28:08,442 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-02-23 19:28:08,584 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 19:28:08,584 INFO L93 Difference]: Finished difference Result 96 states and 99 transitions. [2022-02-23 19:28:08,585 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-02-23 19:28:08,585 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-02-23 19:28:08,585 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 19:28:08,586 INFO L225 Difference]: With dead ends: 96 [2022-02-23 19:28:08,586 INFO L226 Difference]: Without dead ends: 93 [2022-02-23 19:28:08,586 INFO L932 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-02-23 19:28:08,587 INFO L933 BasicCegarLoop]: 42 mSDtfsCounter, 2 mSDsluCounter, 330 mSDsCounter, 0 mSdLazyCounter, 159 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 372 SdHoareTripleChecker+Invalid, 159 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 159 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-02-23 19:28:08,587 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 372 Invalid, 159 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 159 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-02-23 19:28:08,587 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2022-02-23 19:28:08,590 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 93. [2022-02-23 19:28:08,591 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-02-23 19:28:08,591 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 96 transitions. [2022-02-23 19:28:08,591 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 96 transitions. Word has length 66 [2022-02-23 19:28:08,592 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 19:28:08,592 INFO L470 AbstractCegarLoop]: Abstraction has 93 states and 96 transitions. [2022-02-23 19:28:08,604 INFO L471 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-02-23 19:28:08,605 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 96 transitions. [2022-02-23 19:28:08,605 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2022-02-23 19:28:08,606 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 19:28:08,606 INFO L514 BasicCegarLoop]: trace histogram [9, 8, 8, 8, 8, 8, 8, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 19:28:08,615 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-02-23 19:28:08,810 WARN L452 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-02-23 19:28:08,811 INFO L402 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 19:28:08,811 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 19:28:08,811 INFO L85 PathProgramCache]: Analyzing trace with hash 291122568, now seen corresponding path program 7 times [2022-02-23 19:28:08,811 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 19:28:08,811 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1015373062] [2022-02-23 19:28:08,811 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 19:28:08,812 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 19:28:08,819 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 19:28:08,819 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [438890568] [2022-02-23 19:28:08,819 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2022-02-23 19:28:08,819 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 19:28:08,819 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 19:28:08,822 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-02-23 19:28:08,823 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-02-23 19:28:09,292 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 19:28:09,294 INFO L263 TraceCheckSpWp]: Trace formula consists of 228 conjuncts, 37 conjunts are in the unsatisfiable core [2022-02-23 19:28:09,296 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 19:28:09,651 INFO L134 CoverageAnalysis]: Checked inductivity of 240 backedges. 16 proven. 112 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2022-02-23 19:28:09,651 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 19:28:10,219 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 19:28:10,219 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1015373062] [2022-02-23 19:28:10,219 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 19:28:10,219 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [438890568] [2022-02-23 19:28:10,219 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [438890568] provided 0 perfect and 1 imperfect interpolant sequences [2022-02-23 19:28:10,219 INFO L191 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-02-23 19:28:10,219 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2022-02-23 19:28:10,219 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [521072870] [2022-02-23 19:28:10,219 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-02-23 19:28:10,220 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-02-23 19:28:10,220 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 19:28:10,220 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-02-23 19:28:10,220 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=97, Invalid=365, Unknown=0, NotChecked=0, Total=462 [2022-02-23 19:28:10,221 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-02-23 19:28:10,376 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 19:28:10,377 INFO L93 Difference]: Finished difference Result 96 states and 98 transitions. [2022-02-23 19:28:10,377 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-02-23 19:28:10,377 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-02-23 19:28:10,377 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 19:28:10,378 INFO L225 Difference]: With dead ends: 96 [2022-02-23 19:28:10,378 INFO L226 Difference]: Without dead ends: 93 [2022-02-23 19:28:10,378 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 137 GetRequests, 114 SyntacticMatches, 1 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=107, Invalid=445, Unknown=0, NotChecked=0, Total=552 [2022-02-23 19:28:10,379 INFO L933 BasicCegarLoop]: 46 mSDtfsCounter, 2 mSDsluCounter, 396 mSDsCounter, 0 mSdLazyCounter, 196 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 442 SdHoareTripleChecker+Invalid, 196 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 196 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-02-23 19:28:10,379 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 442 Invalid, 196 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 196 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-02-23 19:28:10,380 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2022-02-23 19:28:10,383 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 93. [2022-02-23 19:28:10,383 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-02-23 19:28:10,384 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 95 transitions. [2022-02-23 19:28:10,384 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 95 transitions. Word has length 74 [2022-02-23 19:28:10,384 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 19:28:10,384 INFO L470 AbstractCegarLoop]: Abstraction has 93 states and 95 transitions. [2022-02-23 19:28:10,384 INFO L471 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-02-23 19:28:10,385 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 95 transitions. [2022-02-23 19:28:10,385 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 83 [2022-02-23 19:28:10,385 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 19:28:10,386 INFO L514 BasicCegarLoop]: trace histogram [10, 9, 9, 9, 9, 9, 9, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 19:28:10,394 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-02-23 19:28:10,591 WARN L452 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-02-23 19:28:10,592 INFO L402 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 19:28:10,592 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 19:28:10,592 INFO L85 PathProgramCache]: Analyzing trace with hash 1938494313, now seen corresponding path program 8 times [2022-02-23 19:28:10,592 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 19:28:10,592 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1731404923] [2022-02-23 19:28:10,592 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 19:28:10,592 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 19:28:10,599 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 19:28:10,600 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1684221053] [2022-02-23 19:28:10,600 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-02-23 19:28:10,600 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 19:28:10,600 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 19:28:10,605 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-02-23 19:28:10,606 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-02-23 19:28:11,108 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-02-23 19:28:11,108 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-02-23 19:28:11,109 INFO L263 TraceCheckSpWp]: Trace formula consists of 249 conjuncts, 40 conjunts are in the unsatisfiable core [2022-02-23 19:28:11,111 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 19:28:11,408 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 18 proven. 144 refuted. 0 times theorem prover too weak. 144 trivial. 0 not checked. [2022-02-23 19:28:11,408 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 19:28:11,548 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 19:28:11,548 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1731404923] [2022-02-23 19:28:11,548 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 19:28:11,548 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1684221053] [2022-02-23 19:28:11,549 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1684221053] provided 0 perfect and 1 imperfect interpolant sequences [2022-02-23 19:28:11,549 INFO L191 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-02-23 19:28:11,549 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2022-02-23 19:28:11,549 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1770925893] [2022-02-23 19:28:11,549 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-02-23 19:28:11,549 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-02-23 19:28:11,549 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 19:28:11,550 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-02-23 19:28:11,550 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=227, Unknown=0, NotChecked=0, Total=272 [2022-02-23 19:28:11,550 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-02-23 19:28:11,742 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 19:28:11,742 INFO L93 Difference]: Finished difference Result 96 states and 97 transitions. [2022-02-23 19:28:11,742 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-02-23 19:28:11,742 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-02-23 19:28:11,742 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 19:28:11,743 INFO L225 Difference]: With dead ends: 96 [2022-02-23 19:28:11,743 INFO L226 Difference]: Without dead ends: 93 [2022-02-23 19:28:11,743 INFO L932 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-02-23 19:28:11,744 INFO L933 BasicCegarLoop]: 50 mSDtfsCounter, 2 mSDsluCounter, 468 mSDsCounter, 0 mSdLazyCounter, 237 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 518 SdHoareTripleChecker+Invalid, 237 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 237 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-02-23 19:28:11,744 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 518 Invalid, 237 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 237 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-02-23 19:28:11,744 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2022-02-23 19:28:11,747 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 93. [2022-02-23 19:28:11,747 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-02-23 19:28:11,748 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 94 transitions. [2022-02-23 19:28:11,748 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 94 transitions. Word has length 82 [2022-02-23 19:28:11,748 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 19:28:11,748 INFO L470 AbstractCegarLoop]: Abstraction has 93 states and 94 transitions. [2022-02-23 19:28:11,748 INFO L471 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-02-23 19:28:11,748 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 94 transitions. [2022-02-23 19:28:11,749 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2022-02-23 19:28:11,749 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 19:28:11,749 INFO L514 BasicCegarLoop]: trace histogram [11, 10, 10, 10, 10, 10, 10, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 19:28:11,759 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-02-23 19:28:11,950 WARN L452 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-02-23 19:28:11,950 INFO L402 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 19:28:11,950 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 19:28:11,951 INFO L85 PathProgramCache]: Analyzing trace with hash 757893194, now seen corresponding path program 9 times [2022-02-23 19:28:11,951 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 19:28:11,951 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [678079378] [2022-02-23 19:28:11,951 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 19:28:11,951 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 19:28:11,960 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 19:28:11,960 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1975436477] [2022-02-23 19:28:11,960 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-02-23 19:28:11,961 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 19:28:11,961 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 19:28:11,962 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-02-23 19:28:11,991 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-02-23 19:28:12,509 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2022-02-23 19:28:12,510 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-02-23 19:28:12,512 INFO L263 TraceCheckSpWp]: Trace formula consists of 270 conjuncts, 56 conjunts are in the unsatisfiable core [2022-02-23 19:28:12,514 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 19:28:13,054 INFO L134 CoverageAnalysis]: Checked inductivity of 380 backedges. 66 proven. 182 refuted. 0 times theorem prover too weak. 132 trivial. 0 not checked. [2022-02-23 19:28:13,054 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 19:28:45,364 WARN L838 $PredicateComparison]: unable to prove that (or (= (+ (* c_main_~y~0 c_main_~k~0) c_main_~k~0) (+ (* 2 c_main_~y~0) (* c_main_~y~0 c_main_~y~0) 1)) (<= c_main_~k~0 c_main_~c~0) (not (= (mod (+ (* (- 6) c_main_~y~0 c_main_~y~0 c_main_~y~0) (* (- 13) c_main_~y~0 c_main_~y~0) (* (- 1) c_main_~y~0 c_main_~y~0 c_main_~y~0 c_main_~y~0)) 4) 0)) (< (+ c_main_~c~0 1) c_main_~k~0)) is different from false [2022-02-23 19:28:53,423 WARN L838 $PredicateComparison]: unable to prove that (let ((.cse0 (+ c_main_~y~0 1))) (or (= (+ (* .cse0 c_main_~k~0) c_main_~k~0) (+ (* 2 c_main_~y~0) 3 (* .cse0 .cse0))) (< (+ 2 c_main_~c~0) c_main_~k~0) (not (= (mod (+ (* (- 13) .cse0 .cse0) (* (- 1) .cse0 .cse0 .cse0 .cse0) (* (- 6) .cse0 .cse0 .cse0)) 4) 0)) (<= c_main_~k~0 (+ c_main_~c~0 1)))) is different from false [2022-02-23 19:30:24,194 WARN L838 $PredicateComparison]: unable to prove that (let ((.cse0 (+ 5 c_main_~y~0))) (or (< (+ 6 c_main_~c~0) c_main_~k~0) (= (+ (* .cse0 c_main_~k~0) c_main_~k~0) (+ (* 2 c_main_~y~0) (* .cse0 .cse0) 11)) (not (= (mod (+ (* .cse0 .cse0 .cse0 (- 6)) (* (- 1) .cse0 .cse0 .cse0 .cse0) (* (- 13) .cse0 .cse0)) 4) 0)) (<= c_main_~k~0 (+ 5 c_main_~c~0)))) is different from false [2022-02-23 19:30:51,788 WARN L838 $PredicateComparison]: unable to prove that (let ((.cse0 (+ 7 c_main_~y~0))) (or (< (+ c_main_~c~0 8) c_main_~k~0) (not (= (mod (+ (* (- 13) .cse0 .cse0) (* (- 1) .cse0 .cse0 .cse0 .cse0) (* .cse0 .cse0 .cse0 (- 6))) 4) 0)) (<= c_main_~k~0 (+ 7 c_main_~c~0)) (= (+ (* 2 c_main_~y~0) 15 (* .cse0 .cse0)) (+ c_main_~k~0 (* .cse0 c_main_~k~0))))) is different from false [2022-02-23 19:31:01,855 WARN L838 $PredicateComparison]: unable to prove that (or (not (= (mod (let ((.cse0 (+ 8 c_main_~y~0))) (+ (* (- 13) .cse0 .cse0) (* .cse0 .cse0 .cse0 (- 6)) (* (- 1) .cse0 .cse0 .cse0 .cse0))) 4) 0)) (forall ((main_~k~0 Int)) (or (< (+ 9 c_main_~c~0) main_~k~0) (= (+ (* main_~k~0 9) (* main_~k~0 c_main_~y~0)) (+ (* 18 c_main_~y~0) 81 (* c_main_~y~0 c_main_~y~0))) (<= main_~k~0 (+ c_main_~c~0 8))))) is different from false [2022-02-23 19:31:03,877 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 19:31:03,878 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [678079378] [2022-02-23 19:31:03,878 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 19:31:03,878 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1975436477] [2022-02-23 19:31:03,878 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1975436477] provided 0 perfect and 1 imperfect interpolant sequences [2022-02-23 19:31:03,878 INFO L191 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-02-23 19:31:03,878 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19] total 19 [2022-02-23 19:31:03,878 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1323719459] [2022-02-23 19:31:03,878 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-02-23 19:31:03,878 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2022-02-23 19:31:03,878 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 19:31:03,879 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2022-02-23 19:31:03,879 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=134, Invalid=629, Unknown=13, NotChecked=280, Total=1056 [2022-02-23 19:31:03,879 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-02-23 19:31:04,150 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 19:31:04,150 INFO L93 Difference]: Finished difference Result 98 states and 100 transitions. [2022-02-23 19:31:04,150 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2022-02-23 19:31:04,150 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-02-23 19:31:04,151 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 19:31:04,151 INFO L225 Difference]: With dead ends: 98 [2022-02-23 19:31:04,151 INFO L226 Difference]: Without dead ends: 95 [2022-02-23 19:31:04,152 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 170 GetRequests, 135 SyntacticMatches, 1 SemanticMatches, 34 ConstructedPredicates, 5 IntricatePredicates, 0 DeprecatedPredicates, 91 ImplicationChecksByTransitivity, 102.4s TimeCoverageRelationStatistics Valid=155, Invalid=782, Unknown=13, NotChecked=310, Total=1260 [2022-02-23 19:31:04,152 INFO L933 BasicCegarLoop]: 41 mSDtfsCounter, 10 mSDsluCounter, 518 mSDsCounter, 0 mSdLazyCounter, 386 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 559 SdHoareTripleChecker+Invalid, 388 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 386 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-02-23 19:31:04,152 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 559 Invalid, 388 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 386 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-02-23 19:31:04,153 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 95 states. [2022-02-23 19:31:04,156 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 95 to 95. [2022-02-23 19:31:04,156 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-02-23 19:31:04,156 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 95 states to 95 states and 97 transitions. [2022-02-23 19:31:04,156 INFO L78 Accepts]: Start accepts. Automaton has 95 states and 97 transitions. Word has length 90 [2022-02-23 19:31:04,157 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 19:31:04,157 INFO L470 AbstractCegarLoop]: Abstraction has 95 states and 97 transitions. [2022-02-23 19:31:04,157 INFO L471 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-02-23 19:31:04,157 INFO L276 IsEmpty]: Start isEmpty. Operand 95 states and 97 transitions. [2022-02-23 19:31:04,158 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2022-02-23 19:31:04,158 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 19:31:04,158 INFO L514 BasicCegarLoop]: trace histogram [11, 11, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 19:31:04,168 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-02-23 19:31:04,358 WARN L452 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-02-23 19:31:04,359 INFO L402 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 19:31:04,359 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 19:31:04,359 INFO L85 PathProgramCache]: Analyzing trace with hash -953190739, now seen corresponding path program 3 times [2022-02-23 19:31:04,359 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 19:31:04,359 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2112685148] [2022-02-23 19:31:04,359 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 19:31:04,360 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 19:31:04,366 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 19:31:04,366 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [131560537] [2022-02-23 19:31:04,366 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-02-23 19:31:04,366 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 19:31:04,366 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 19:31:04,369 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-02-23 19:31:04,370 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-02-23 19:31:04,427 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 11 check-sat command(s) [2022-02-23 19:31:04,428 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-02-23 19:31:04,429 INFO L263 TraceCheckSpWp]: Trace formula consists of 281 conjuncts, 25 conjunts are in the unsatisfiable core [2022-02-23 19:31:04,430 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 19:31:04,625 INFO L134 CoverageAnalysis]: Checked inductivity of 400 backedges. 20 proven. 380 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-02-23 19:31:04,626 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 19:31:04,906 INFO L134 CoverageAnalysis]: Checked inductivity of 400 backedges. 20 proven. 200 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2022-02-23 19:31:04,906 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 19:31:04,907 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2112685148] [2022-02-23 19:31:04,907 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 19:31:04,907 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [131560537] [2022-02-23 19:31:04,907 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [131560537] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-23 19:31:04,907 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-23 19:31:04,907 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 26 [2022-02-23 19:31:04,907 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [433060572] [2022-02-23 19:31:04,907 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-23 19:31:04,908 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2022-02-23 19:31:04,908 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 19:31:04,908 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2022-02-23 19:31:04,908 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=281, Invalid=369, Unknown=0, NotChecked=0, Total=650 [2022-02-23 19:31:04,909 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-02-23 19:31:05,320 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 19:31:05,320 INFO L93 Difference]: Finished difference Result 244 states and 245 transitions. [2022-02-23 19:31:05,320 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 46 states. [2022-02-23 19:31:05,320 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-02-23 19:31:05,321 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 19:31:05,322 INFO L225 Difference]: With dead ends: 244 [2022-02-23 19:31:05,322 INFO L226 Difference]: Without dead ends: 244 [2022-02-23 19:31:05,323 INFO L932 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-02-23 19:31:05,323 INFO L933 BasicCegarLoop]: 38 mSDtfsCounter, 296 mSDsluCounter, 212 mSDsCounter, 0 mSdLazyCounter, 127 mSolverCounterSat, 109 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 296 SdHoareTripleChecker+Valid, 250 SdHoareTripleChecker+Invalid, 236 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 109 IncrementalHoareTripleChecker+Valid, 127 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-02-23 19:31:05,323 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [296 Valid, 250 Invalid, 236 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [109 Valid, 127 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-02-23 19:31:05,324 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 244 states. [2022-02-23 19:31:05,329 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 244 to 189. [2022-02-23 19:31:05,329 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-02-23 19:31:05,330 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 189 states to 189 states and 201 transitions. [2022-02-23 19:31:05,330 INFO L78 Accepts]: Start accepts. Automaton has 189 states and 201 transitions. Word has length 92 [2022-02-23 19:31:05,330 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 19:31:05,330 INFO L470 AbstractCegarLoop]: Abstraction has 189 states and 201 transitions. [2022-02-23 19:31:05,331 INFO L471 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-02-23 19:31:05,331 INFO L276 IsEmpty]: Start isEmpty. Operand 189 states and 201 transitions. [2022-02-23 19:31:05,332 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 99 [2022-02-23 19:31:05,333 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 19:31:05,333 INFO L514 BasicCegarLoop]: trace histogram [12, 11, 11, 11, 11, 11, 11, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 19:31:05,355 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-02-23 19:31:05,545 WARN L452 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-02-23 19:31:05,546 INFO L402 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 19:31:05,546 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 19:31:05,546 INFO L85 PathProgramCache]: Analyzing trace with hash 138382379, now seen corresponding path program 10 times [2022-02-23 19:31:05,546 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 19:31:05,546 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1878181579] [2022-02-23 19:31:05,546 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 19:31:05,546 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 19:31:05,554 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 19:31:05,554 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [406313822] [2022-02-23 19:31:05,554 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-02-23 19:31:05,554 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 19:31:05,554 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 19:31:05,558 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-02-23 19:31:05,562 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-02-23 19:31:06,756 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-02-23 19:31:06,757 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-02-23 19:31:06,758 INFO L263 TraceCheckSpWp]: Trace formula consists of 291 conjuncts, 48 conjunts are in the unsatisfiable core [2022-02-23 19:31:06,760 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 19:31:07,116 INFO L134 CoverageAnalysis]: Checked inductivity of 462 backedges. 22 proven. 220 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2022-02-23 19:31:07,116 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 19:31:07,234 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 19:31:07,234 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1878181579] [2022-02-23 19:31:07,234 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 19:31:07,234 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [406313822] [2022-02-23 19:31:07,234 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [406313822] provided 0 perfect and 1 imperfect interpolant sequences [2022-02-23 19:31:07,235 INFO L191 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-02-23 19:31:07,235 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2022-02-23 19:31:07,235 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [3894808] [2022-02-23 19:31:07,235 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-02-23 19:31:07,235 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-02-23 19:31:07,235 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 19:31:07,236 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-02-23 19:31:07,236 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=291, Unknown=0, NotChecked=0, Total=342 [2022-02-23 19:31:07,236 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-02-23 19:31:07,451 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 19:31:07,452 INFO L93 Difference]: Finished difference Result 192 states and 203 transitions. [2022-02-23 19:31:07,452 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2022-02-23 19:31:07,452 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-02-23 19:31:07,452 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 19:31:07,453 INFO L225 Difference]: With dead ends: 192 [2022-02-23 19:31:07,453 INFO L226 Difference]: Without dead ends: 189 [2022-02-23 19:31:07,453 INFO L932 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-02-23 19:31:07,454 INFO L933 BasicCegarLoop]: 58 mSDtfsCounter, 2 mSDsluCounter, 630 mSDsCounter, 0 mSdLazyCounter, 331 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 688 SdHoareTripleChecker+Invalid, 331 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 331 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-02-23 19:31:07,454 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 688 Invalid, 331 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 331 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-02-23 19:31:07,454 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 189 states. [2022-02-23 19:31:07,458 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 189 to 189. [2022-02-23 19:31:07,458 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-02-23 19:31:07,459 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 189 states to 189 states and 200 transitions. [2022-02-23 19:31:07,459 INFO L78 Accepts]: Start accepts. Automaton has 189 states and 200 transitions. Word has length 98 [2022-02-23 19:31:07,459 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 19:31:07,459 INFO L470 AbstractCegarLoop]: Abstraction has 189 states and 200 transitions. [2022-02-23 19:31:07,459 INFO L471 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-02-23 19:31:07,459 INFO L276 IsEmpty]: Start isEmpty. Operand 189 states and 200 transitions. [2022-02-23 19:31:07,460 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 107 [2022-02-23 19:31:07,460 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 19:31:07,460 INFO L514 BasicCegarLoop]: trace histogram [13, 12, 12, 12, 12, 12, 12, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 19:31:07,468 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Ended with exit code 0 [2022-02-23 19:31:07,666 WARN L452 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-02-23 19:31:07,666 INFO L402 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 19:31:07,667 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 19:31:07,667 INFO L85 PathProgramCache]: Analyzing trace with hash 1036328716, now seen corresponding path program 11 times [2022-02-23 19:31:07,667 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 19:31:07,667 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1199704147] [2022-02-23 19:31:07,667 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 19:31:07,667 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 19:31:07,675 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 19:31:07,675 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1674776510] [2022-02-23 19:31:07,675 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-02-23 19:31:07,675 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 19:31:07,675 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 19:31:07,676 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-02-23 19:31:07,706 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-02-23 19:31:08,244 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 12 check-sat command(s) [2022-02-23 19:31:08,244 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-02-23 19:31:08,246 INFO L263 TraceCheckSpWp]: Trace formula consists of 312 conjuncts, 52 conjunts are in the unsatisfiable core [2022-02-23 19:31:08,247 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 19:31:08,605 INFO L134 CoverageAnalysis]: Checked inductivity of 552 backedges. 24 proven. 264 refuted. 0 times theorem prover too weak. 264 trivial. 0 not checked. [2022-02-23 19:31:08,605 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 19:31:08,741 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 19:31:08,741 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1199704147] [2022-02-23 19:31:08,741 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 19:31:08,741 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1674776510] [2022-02-23 19:31:08,741 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1674776510] provided 0 perfect and 1 imperfect interpolant sequences [2022-02-23 19:31:08,741 INFO L191 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-02-23 19:31:08,741 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2022-02-23 19:31:08,741 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1420442058] [2022-02-23 19:31:08,741 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-02-23 19:31:08,742 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2022-02-23 19:31:08,742 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 19:31:08,742 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2022-02-23 19:31:08,742 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=326, Unknown=0, NotChecked=0, Total=380 [2022-02-23 19:31:08,742 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-02-23 19:31:08,959 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 19:31:08,959 INFO L93 Difference]: Finished difference Result 192 states and 202 transitions. [2022-02-23 19:31:08,960 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2022-02-23 19:31:08,960 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-02-23 19:31:08,960 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 19:31:08,961 INFO L225 Difference]: With dead ends: 192 [2022-02-23 19:31:08,961 INFO L226 Difference]: Without dead ends: 189 [2022-02-23 19:31:08,961 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 121 GetRequests, 100 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=64, Invalid=398, Unknown=0, NotChecked=0, Total=462 [2022-02-23 19:31:08,962 INFO L933 BasicCegarLoop]: 62 mSDtfsCounter, 2 mSDsluCounter, 720 mSDsCounter, 0 mSdLazyCounter, 384 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 782 SdHoareTripleChecker+Invalid, 384 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 384 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-02-23 19:31:08,962 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 782 Invalid, 384 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 384 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-02-23 19:31:08,962 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 189 states. [2022-02-23 19:31:08,966 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 189 to 189. [2022-02-23 19:31:08,966 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-02-23 19:31:08,967 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 189 states to 189 states and 199 transitions. [2022-02-23 19:31:08,967 INFO L78 Accepts]: Start accepts. Automaton has 189 states and 199 transitions. Word has length 106 [2022-02-23 19:31:08,967 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 19:31:08,967 INFO L470 AbstractCegarLoop]: Abstraction has 189 states and 199 transitions. [2022-02-23 19:31:08,968 INFO L471 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-02-23 19:31:08,968 INFO L276 IsEmpty]: Start isEmpty. Operand 189 states and 199 transitions. [2022-02-23 19:31:08,968 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 115 [2022-02-23 19:31:08,968 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 19:31:08,969 INFO L514 BasicCegarLoop]: trace histogram [14, 13, 13, 13, 13, 13, 13, 12, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 19:31:08,979 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-02-23 19:31:09,174 WARN L452 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-02-23 19:31:09,175 INFO L402 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 19:31:09,175 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 19:31:09,175 INFO L85 PathProgramCache]: Analyzing trace with hash 1975402733, now seen corresponding path program 12 times [2022-02-23 19:31:09,175 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 19:31:09,175 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [643370960] [2022-02-23 19:31:09,175 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 19:31:09,175 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 19:31:09,187 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 19:31:09,188 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1755228579] [2022-02-23 19:31:09,188 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-02-23 19:31:09,188 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 19:31:09,188 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 19:31:09,192 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-02-23 19:31:09,193 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-02-23 19:31:09,698 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 13 check-sat command(s) [2022-02-23 19:31:09,698 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-02-23 19:31:09,700 INFO L263 TraceCheckSpWp]: Trace formula consists of 333 conjuncts, 56 conjunts are in the unsatisfiable core [2022-02-23 19:31:09,702 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 19:31:10,087 INFO L134 CoverageAnalysis]: Checked inductivity of 650 backedges. 26 proven. 312 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2022-02-23 19:31:10,087 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 19:31:10,206 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 19:31:10,206 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [643370960] [2022-02-23 19:31:10,206 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 19:31:10,206 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1755228579] [2022-02-23 19:31:10,206 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1755228579] provided 0 perfect and 1 imperfect interpolant sequences [2022-02-23 19:31:10,206 INFO L191 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-02-23 19:31:10,206 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18] total 18 [2022-02-23 19:31:10,206 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [740768295] [2022-02-23 19:31:10,206 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-02-23 19:31:10,207 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2022-02-23 19:31:10,207 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 19:31:10,207 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2022-02-23 19:31:10,207 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=57, Invalid=363, Unknown=0, NotChecked=0, Total=420 [2022-02-23 19:31:10,207 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-02-23 19:31:10,451 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 19:31:10,451 INFO L93 Difference]: Finished difference Result 192 states and 201 transitions. [2022-02-23 19:31:10,451 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2022-02-23 19:31:10,451 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-02-23 19:31:10,452 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 19:31:10,452 INFO L225 Difference]: With dead ends: 192 [2022-02-23 19:31:10,453 INFO L226 Difference]: Without dead ends: 189 [2022-02-23 19:31:10,453 INFO L932 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-02-23 19:31:10,453 INFO L933 BasicCegarLoop]: 66 mSDtfsCounter, 2 mSDsluCounter, 816 mSDsCounter, 0 mSdLazyCounter, 441 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 882 SdHoareTripleChecker+Invalid, 441 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 441 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-02-23 19:31:10,454 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 882 Invalid, 441 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 441 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-02-23 19:31:10,454 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 189 states. [2022-02-23 19:31:10,457 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 189 to 189. [2022-02-23 19:31:10,458 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-02-23 19:31:10,458 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 189 states to 189 states and 198 transitions. [2022-02-23 19:31:10,458 INFO L78 Accepts]: Start accepts. Automaton has 189 states and 198 transitions. Word has length 114 [2022-02-23 19:31:10,459 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 19:31:10,459 INFO L470 AbstractCegarLoop]: Abstraction has 189 states and 198 transitions. [2022-02-23 19:31:10,459 INFO L471 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-02-23 19:31:10,459 INFO L276 IsEmpty]: Start isEmpty. Operand 189 states and 198 transitions. [2022-02-23 19:31:10,460 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 123 [2022-02-23 19:31:10,460 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 19:31:10,460 INFO L514 BasicCegarLoop]: trace histogram [15, 14, 14, 14, 14, 14, 14, 13, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 19:31:10,468 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-02-23 19:31:10,665 WARN L452 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-02-23 19:31:10,666 INFO L402 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 19:31:10,666 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 19:31:10,666 INFO L85 PathProgramCache]: Analyzing trace with hash -953421362, now seen corresponding path program 13 times [2022-02-23 19:31:10,666 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 19:31:10,666 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1042428966] [2022-02-23 19:31:10,666 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 19:31:10,667 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 19:31:10,681 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 19:31:10,681 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1999448122] [2022-02-23 19:31:10,681 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2022-02-23 19:31:10,681 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 19:31:10,681 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 19:31:10,682 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-02-23 19:31:10,703 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-02-23 19:31:11,735 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 19:31:11,737 INFO L263 TraceCheckSpWp]: Trace formula consists of 354 conjuncts, 67 conjunts are in the unsatisfiable core [2022-02-23 19:31:11,739 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 19:31:12,181 INFO L134 CoverageAnalysis]: Checked inductivity of 756 backedges. 66 proven. 365 refuted. 0 times theorem prover too weak. 325 trivial. 0 not checked. [2022-02-23 19:31:12,181 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 19:31:16,363 WARN L838 $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-02-23 19:31:18,381 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 19:31:18,381 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1042428966] [2022-02-23 19:31:18,381 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 19:31:18,381 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1999448122] [2022-02-23 19:31:18,381 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1999448122] provided 0 perfect and 1 imperfect interpolant sequences [2022-02-23 19:31:18,382 INFO L191 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-02-23 19:31:18,382 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2022-02-23 19:31:18,382 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [562983665] [2022-02-23 19:31:18,382 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-02-23 19:31:18,382 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2022-02-23 19:31:18,382 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 19:31:18,383 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2022-02-23 19:31:18,383 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=539, Unknown=1, NotChecked=46, Total=650 [2022-02-23 19:31:18,383 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-02-23 19:31:18,718 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 19:31:18,718 INFO L93 Difference]: Finished difference Result 192 states and 200 transitions. [2022-02-23 19:31:18,719 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2022-02-23 19:31:18,719 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-02-23 19:31:18,719 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 19:31:18,720 INFO L225 Difference]: With dead ends: 192 [2022-02-23 19:31:18,720 INFO L226 Difference]: Without dead ends: 189 [2022-02-23 19:31:18,720 INFO L932 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-02-23 19:31:18,721 INFO L933 BasicCegarLoop]: 53 mSDtfsCounter, 7 mSDsluCounter, 876 mSDsCounter, 0 mSdLazyCounter, 641 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 929 SdHoareTripleChecker+Invalid, 642 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 641 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-02-23 19:31:18,721 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [7 Valid, 929 Invalid, 642 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 641 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-02-23 19:31:18,722 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 189 states. [2022-02-23 19:31:18,725 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 189 to 189. [2022-02-23 19:31:18,725 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-02-23 19:31:18,726 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 189 states to 189 states and 197 transitions. [2022-02-23 19:31:18,726 INFO L78 Accepts]: Start accepts. Automaton has 189 states and 197 transitions. Word has length 122 [2022-02-23 19:31:18,726 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 19:31:18,726 INFO L470 AbstractCegarLoop]: Abstraction has 189 states and 197 transitions. [2022-02-23 19:31:18,726 INFO L471 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-02-23 19:31:18,726 INFO L276 IsEmpty]: Start isEmpty. Operand 189 states and 197 transitions. [2022-02-23 19:31:18,727 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 131 [2022-02-23 19:31:18,727 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 19:31:18,727 INFO L514 BasicCegarLoop]: trace histogram [16, 15, 15, 15, 15, 15, 15, 14, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 19:31:18,739 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Ended with exit code 0 [2022-02-23 19:31:18,934 WARN L452 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-02-23 19:31:18,934 INFO L402 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 19:31:18,934 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 19:31:18,934 INFO L85 PathProgramCache]: Analyzing trace with hash -1206963793, now seen corresponding path program 14 times [2022-02-23 19:31:18,934 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 19:31:18,934 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1494762697] [2022-02-23 19:31:18,934 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 19:31:18,935 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 19:31:18,940 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 19:31:18,940 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2011218384] [2022-02-23 19:31:18,940 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-02-23 19:31:18,941 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 19:31:18,941 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 19:31:18,942 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-02-23 19:31:18,952 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-02-23 19:31:19,786 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-02-23 19:31:19,786 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-02-23 19:31:19,788 INFO L263 TraceCheckSpWp]: Trace formula consists of 375 conjuncts, 64 conjunts are in the unsatisfiable core [2022-02-23 19:31:19,790 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 19:31:20,225 INFO L134 CoverageAnalysis]: Checked inductivity of 870 backedges. 30 proven. 420 refuted. 0 times theorem prover too weak. 420 trivial. 0 not checked. [2022-02-23 19:31:20,226 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 19:31:20,430 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 19:31:20,430 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1494762697] [2022-02-23 19:31:20,430 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 19:31:20,430 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2011218384] [2022-02-23 19:31:20,430 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2011218384] provided 0 perfect and 1 imperfect interpolant sequences [2022-02-23 19:31:20,430 INFO L191 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-02-23 19:31:20,430 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20] total 20 [2022-02-23 19:31:20,431 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1997391651] [2022-02-23 19:31:20,431 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-02-23 19:31:20,431 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2022-02-23 19:31:20,431 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 19:31:20,432 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2022-02-23 19:31:20,432 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=63, Invalid=443, Unknown=0, NotChecked=0, Total=506 [2022-02-23 19:31:20,432 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-02-23 19:31:20,772 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 19:31:20,773 INFO L93 Difference]: Finished difference Result 192 states and 199 transitions. [2022-02-23 19:31:20,773 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2022-02-23 19:31:20,773 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-02-23 19:31:20,774 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 19:31:20,774 INFO L225 Difference]: With dead ends: 192 [2022-02-23 19:31:20,774 INFO L226 Difference]: Without dead ends: 189 [2022-02-23 19:31:20,775 INFO L932 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-02-23 19:31:20,775 INFO L933 BasicCegarLoop]: 74 mSDtfsCounter, 2 mSDsluCounter, 1026 mSDsCounter, 0 mSdLazyCounter, 567 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 1100 SdHoareTripleChecker+Invalid, 567 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 567 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-02-23 19:31:20,775 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 1100 Invalid, 567 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 567 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-02-23 19:31:20,776 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 189 states. [2022-02-23 19:31:20,779 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 189 to 189. [2022-02-23 19:31:20,779 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-02-23 19:31:20,780 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 189 states to 189 states and 196 transitions. [2022-02-23 19:31:20,780 INFO L78 Accepts]: Start accepts. Automaton has 189 states and 196 transitions. Word has length 130 [2022-02-23 19:31:20,780 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 19:31:20,780 INFO L470 AbstractCegarLoop]: Abstraction has 189 states and 196 transitions. [2022-02-23 19:31:20,781 INFO L471 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-02-23 19:31:20,781 INFO L276 IsEmpty]: Start isEmpty. Operand 189 states and 196 transitions. [2022-02-23 19:31:20,781 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 139 [2022-02-23 19:31:20,781 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 19:31:20,781 INFO L514 BasicCegarLoop]: trace histogram [17, 16, 16, 16, 16, 16, 16, 15, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 19:31:20,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-02-23 19:31:20,983 WARN L452 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-02-23 19:31:20,983 INFO L402 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 19:31:20,983 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 19:31:20,984 INFO L85 PathProgramCache]: Analyzing trace with hash 1030291600, now seen corresponding path program 15 times [2022-02-23 19:31:20,984 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 19:31:20,984 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [582526836] [2022-02-23 19:31:20,984 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 19:31:20,984 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 19:31:20,992 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 19:31:20,992 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1578912660] [2022-02-23 19:31:20,993 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-02-23 19:31:20,993 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 19:31:20,993 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 19:31:20,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-02-23 19:31:20,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-02-23 19:31:21,651 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 16 check-sat command(s) [2022-02-23 19:31:21,651 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-02-23 19:31:21,654 INFO L263 TraceCheckSpWp]: Trace formula consists of 396 conjuncts, 69 conjunts are in the unsatisfiable core [2022-02-23 19:31:21,656 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 19:31:22,291 INFO L134 CoverageAnalysis]: Checked inductivity of 992 backedges. 32 proven. 480 refuted. 0 times theorem prover too weak. 480 trivial. 0 not checked. [2022-02-23 19:31:22,292 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 19:31:23,553 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 19:31:23,554 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [582526836] [2022-02-23 19:31:23,554 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 19:31:23,554 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1578912660] [2022-02-23 19:31:23,554 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1578912660] provided 0 perfect and 1 imperfect interpolant sequences [2022-02-23 19:31:23,554 INFO L191 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-02-23 19:31:23,554 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2022-02-23 19:31:23,554 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1030703468] [2022-02-23 19:31:23,554 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-02-23 19:31:23,554 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2022-02-23 19:31:23,554 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 19:31:23,555 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2022-02-23 19:31:23,555 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=305, Invalid=1101, Unknown=0, NotChecked=0, Total=1406 [2022-02-23 19:31:23,555 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-02-23 19:31:23,946 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 19:31:23,946 INFO L93 Difference]: Finished difference Result 192 states and 198 transitions. [2022-02-23 19:31:23,948 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2022-02-23 19:31:23,948 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-02-23 19:31:23,948 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 19:31:23,949 INFO L225 Difference]: With dead ends: 192 [2022-02-23 19:31:23,949 INFO L226 Difference]: Without dead ends: 189 [2022-02-23 19:31:23,950 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 265 GetRequests, 226 SyntacticMatches, 1 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 31 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=315, Invalid=1245, Unknown=0, NotChecked=0, Total=1560 [2022-02-23 19:31:23,950 INFO L933 BasicCegarLoop]: 78 mSDtfsCounter, 2 mSDsluCounter, 1140 mSDsCounter, 0 mSdLazyCounter, 636 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 1218 SdHoareTripleChecker+Invalid, 636 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 636 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-02-23 19:31:23,950 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 1218 Invalid, 636 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 636 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-02-23 19:31:23,951 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 189 states. [2022-02-23 19:31:23,954 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 189 to 189. [2022-02-23 19:31:23,954 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-02-23 19:31:23,955 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 189 states to 189 states and 195 transitions. [2022-02-23 19:31:23,955 INFO L78 Accepts]: Start accepts. Automaton has 189 states and 195 transitions. Word has length 138 [2022-02-23 19:31:23,955 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 19:31:23,955 INFO L470 AbstractCegarLoop]: Abstraction has 189 states and 195 transitions. [2022-02-23 19:31:23,955 INFO L471 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-02-23 19:31:23,956 INFO L276 IsEmpty]: Start isEmpty. Operand 189 states and 195 transitions. [2022-02-23 19:31:23,956 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 147 [2022-02-23 19:31:23,956 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 19:31:23,956 INFO L514 BasicCegarLoop]: trace histogram [18, 17, 17, 17, 17, 17, 17, 16, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 19:31:23,963 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-02-23 19:31:24,163 WARN L452 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-02-23 19:31:24,164 INFO L402 AbstractCegarLoop]: === Iteration 23 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 19:31:24,164 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 19:31:24,164 INFO L85 PathProgramCache]: Analyzing trace with hash -1153802639, now seen corresponding path program 16 times [2022-02-23 19:31:24,164 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 19:31:24,164 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1120544360] [2022-02-23 19:31:24,164 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 19:31:24,165 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 19:31:24,171 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 19:31:24,172 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [222703177] [2022-02-23 19:31:24,172 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-02-23 19:31:24,172 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 19:31:24,172 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 19:31:24,173 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-02-23 19:31:24,183 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-02-23 19:31:25,079 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-02-23 19:31:25,079 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-02-23 19:31:25,082 INFO L263 TraceCheckSpWp]: Trace formula consists of 417 conjuncts, 72 conjunts are in the unsatisfiable core [2022-02-23 19:31:25,084 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 19:31:25,572 INFO L134 CoverageAnalysis]: Checked inductivity of 1122 backedges. 34 proven. 544 refuted. 0 times theorem prover too weak. 544 trivial. 0 not checked. [2022-02-23 19:31:25,572 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 19:31:25,712 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 19:31:25,712 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1120544360] [2022-02-23 19:31:25,712 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 19:31:25,712 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [222703177] [2022-02-23 19:31:25,712 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [222703177] provided 0 perfect and 1 imperfect interpolant sequences [2022-02-23 19:31:25,712 INFO L191 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-02-23 19:31:25,712 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22] total 22 [2022-02-23 19:31:25,712 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1235281822] [2022-02-23 19:31:25,712 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-02-23 19:31:25,713 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2022-02-23 19:31:25,713 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 19:31:25,713 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2022-02-23 19:31:25,713 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=69, Invalid=531, Unknown=0, NotChecked=0, Total=600 [2022-02-23 19:31:25,713 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-02-23 19:31:26,100 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 19:31:26,100 INFO L93 Difference]: Finished difference Result 192 states and 197 transitions. [2022-02-23 19:31:26,101 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2022-02-23 19:31:26,101 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-02-23 19:31:26,101 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 19:31:26,102 INFO L225 Difference]: With dead ends: 192 [2022-02-23 19:31:26,102 INFO L226 Difference]: Without dead ends: 189 [2022-02-23 19:31:26,102 INFO L932 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-02-23 19:31:26,102 INFO L933 BasicCegarLoop]: 82 mSDtfsCounter, 2 mSDsluCounter, 1260 mSDsCounter, 0 mSdLazyCounter, 709 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 1342 SdHoareTripleChecker+Invalid, 709 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 709 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-02-23 19:31:26,103 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 1342 Invalid, 709 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 709 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2022-02-23 19:31:26,103 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 189 states. [2022-02-23 19:31:26,110 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 189 to 189. [2022-02-23 19:31:26,111 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-02-23 19:31:26,114 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 189 states to 189 states and 194 transitions. [2022-02-23 19:31:26,114 INFO L78 Accepts]: Start accepts. Automaton has 189 states and 194 transitions. Word has length 146 [2022-02-23 19:31:26,114 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 19:31:26,115 INFO L470 AbstractCegarLoop]: Abstraction has 189 states and 194 transitions. [2022-02-23 19:31:26,115 INFO L471 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-02-23 19:31:26,115 INFO L276 IsEmpty]: Start isEmpty. Operand 189 states and 194 transitions. [2022-02-23 19:31:26,116 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 155 [2022-02-23 19:31:26,116 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 19:31:26,116 INFO L514 BasicCegarLoop]: trace histogram [19, 18, 18, 18, 18, 18, 18, 17, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 19:31:26,127 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-02-23 19:31:26,323 WARN L452 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-02-23 19:31:26,323 INFO L402 AbstractCegarLoop]: === Iteration 24 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 19:31:26,323 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 19:31:26,324 INFO L85 PathProgramCache]: Analyzing trace with hash 75778898, now seen corresponding path program 17 times [2022-02-23 19:31:26,324 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 19:31:26,324 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1179411965] [2022-02-23 19:31:26,324 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 19:31:26,324 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 19:31:26,341 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 19:31:26,341 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1133500580] [2022-02-23 19:31:26,341 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-02-23 19:31:26,341 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 19:31:26,341 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 19:31:26,342 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-02-23 19:31:26,344 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (24)] Waiting until timeout for monitored process