/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/AutomizerC.xml -s ../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationJordan_32.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/cohencu-ll_valuebound20.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-5d317bd [2022-03-19 03:40:37,280 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-03-19 03:40:37,283 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-03-19 03:40:37,315 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-03-19 03:40:37,315 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-03-19 03:40:37,316 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-03-19 03:40:37,320 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-03-19 03:40:37,325 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-03-19 03:40:37,327 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-03-19 03:40:37,335 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-03-19 03:40:37,336 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-03-19 03:40:37,336 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-03-19 03:40:37,337 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-03-19 03:40:37,337 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-03-19 03:40:37,338 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-03-19 03:40:37,339 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-03-19 03:40:37,339 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-03-19 03:40:37,340 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-03-19 03:40:37,341 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-03-19 03:40:37,342 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-03-19 03:40:37,343 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-03-19 03:40:37,347 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-03-19 03:40:37,348 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-03-19 03:40:37,349 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-03-19 03:40:37,351 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-03-19 03:40:37,361 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-03-19 03:40:37,361 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-03-19 03:40:37,361 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-03-19 03:40:37,362 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-03-19 03:40:37,362 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-03-19 03:40:37,363 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-03-19 03:40:37,363 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-03-19 03:40:37,364 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-03-19 03:40:37,364 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-03-19 03:40:37,365 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-03-19 03:40:37,365 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-03-19 03:40:37,366 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-03-19 03:40:37,366 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-03-19 03:40:37,366 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-03-19 03:40:37,367 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-03-19 03:40:37,367 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-03-19 03:40:37,374 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-03-19 03:40:37,375 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationJordan_32.epf [2022-03-19 03:40:37,387 INFO L113 SettingsManager]: Loading preferences was successful [2022-03-19 03:40:37,387 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-03-19 03:40:37,388 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-03-19 03:40:37,389 INFO L138 SettingsManager]: * sizeof long=4 [2022-03-19 03:40:37,389 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-03-19 03:40:37,389 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-03-19 03:40:37,389 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-03-19 03:40:37,389 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-03-19 03:40:37,389 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-03-19 03:40:37,389 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-03-19 03:40:37,389 INFO L138 SettingsManager]: * sizeof long double=12 [2022-03-19 03:40:37,390 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-03-19 03:40:37,390 INFO L138 SettingsManager]: * Use constant arrays=true [2022-03-19 03:40:37,390 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-03-19 03:40:37,390 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-03-19 03:40:37,390 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-03-19 03:40:37,390 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-03-19 03:40:37,390 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-03-19 03:40:37,390 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-19 03:40:37,391 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-03-19 03:40:37,391 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-03-19 03:40:37,391 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-03-19 03:40:37,391 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-03-19 03:40:37,391 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-03-19 03:40:37,391 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=JORDAN [2022-03-19 03:40:37,391 INFO L138 SettingsManager]: * Use separate solver for trace checks=false WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-03-19 03:40:37,600 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-03-19 03:40:37,623 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-03-19 03:40:37,625 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-03-19 03:40:37,626 INFO L271 PluginConnector]: Initializing CDTParser... [2022-03-19 03:40:37,626 INFO L275 PluginConnector]: CDTParser initialized [2022-03-19 03:40:37,627 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/cohencu-ll_valuebound20.c [2022-03-19 03:40:37,691 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/5a6bbe1af/cbb7ba4b58014b6587afa8b866cb58ce/FLAG5b6d639f4 [2022-03-19 03:40:38,045 INFO L306 CDTParser]: Found 1 translation units. [2022-03-19 03:40:38,046 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/cohencu-ll_valuebound20.c [2022-03-19 03:40:38,052 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/5a6bbe1af/cbb7ba4b58014b6587afa8b866cb58ce/FLAG5b6d639f4 [2022-03-19 03:40:38,064 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/5a6bbe1af/cbb7ba4b58014b6587afa8b866cb58ce [2022-03-19 03:40:38,066 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-03-19 03:40:38,067 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-03-19 03:40:38,070 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-03-19 03:40:38,070 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-03-19 03:40:38,073 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-03-19 03:40:38,074 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.03 03:40:38" (1/1) ... [2022-03-19 03:40:38,076 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@297c57a4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.03 03:40:38, skipping insertion in model container [2022-03-19 03:40:38,076 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.03 03:40:38" (1/1) ... [2022-03-19 03:40:38,081 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-03-19 03:40:38,093 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-03-19 03:40:38,296 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/cohencu-ll_valuebound20.c[588,601] [2022-03-19 03:40:38,314 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-19 03:40:38,320 INFO L203 MainTranslator]: Completed pre-run [2022-03-19 03:40:38,331 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/cohencu-ll_valuebound20.c[588,601] [2022-03-19 03:40:38,339 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-19 03:40:38,349 INFO L208 MainTranslator]: Completed translation [2022-03-19 03:40:38,350 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.03 03:40:38 WrapperNode [2022-03-19 03:40:38,350 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-03-19 03:40:38,351 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-03-19 03:40:38,351 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-03-19 03:40:38,351 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-03-19 03:40:38,358 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.03 03:40:38" (1/1) ... [2022-03-19 03:40:38,358 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.03 03:40:38" (1/1) ... [2022-03-19 03:40:38,364 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.03 03:40:38" (1/1) ... [2022-03-19 03:40:38,364 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.03 03:40:38" (1/1) ... [2022-03-19 03:40:38,368 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.03 03:40:38" (1/1) ... [2022-03-19 03:40:38,370 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.03 03:40:38" (1/1) ... [2022-03-19 03:40:38,371 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.03 03:40:38" (1/1) ... [2022-03-19 03:40:38,373 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-03-19 03:40:38,373 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-03-19 03:40:38,373 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-03-19 03:40:38,373 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-03-19 03:40:38,374 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.03 03:40:38" (1/1) ... [2022-03-19 03:40:38,384 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-19 03:40:38,394 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-19 03:40:38,407 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-03-19 03:40:38,408 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-03-19 03:40:38,436 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-03-19 03:40:38,436 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-03-19 03:40:38,436 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-03-19 03:40:38,436 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-03-19 03:40:38,436 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-03-19 03:40:38,436 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-03-19 03:40:38,436 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-03-19 03:40:38,437 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-03-19 03:40:38,437 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-03-19 03:40:38,437 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-03-19 03:40:38,437 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_ushort [2022-03-19 03:40:38,437 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-03-19 03:40:38,437 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-03-19 03:40:38,437 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-03-19 03:40:38,437 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-03-19 03:40:38,437 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-03-19 03:40:38,438 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-03-19 03:40:38,438 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-03-19 03:40:38,438 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-03-19 03:40:38,438 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-03-19 03:40:38,488 INFO L234 CfgBuilder]: Building ICFG [2022-03-19 03:40:38,489 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-03-19 03:40:38,588 INFO L275 CfgBuilder]: Performing block encoding [2022-03-19 03:40:38,593 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-03-19 03:40:38,594 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-03-19 03:40:38,595 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.03 03:40:38 BoogieIcfgContainer [2022-03-19 03:40:38,595 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-03-19 03:40:38,597 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-03-19 03:40:38,597 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-03-19 03:40:38,605 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-03-19 03:40:38,605 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 19.03 03:40:38" (1/3) ... [2022-03-19 03:40:38,606 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1c273be7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.03 03:40:38, skipping insertion in model container [2022-03-19 03:40:38,606 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.03 03:40:38" (2/3) ... [2022-03-19 03:40:38,606 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1c273be7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.03 03:40:38, skipping insertion in model container [2022-03-19 03:40:38,607 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.03 03:40:38" (3/3) ... [2022-03-19 03:40:38,608 INFO L111 eAbstractionObserver]: Analyzing ICFG cohencu-ll_valuebound20.c [2022-03-19 03:40:38,612 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-03-19 03:40:38,612 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-03-19 03:40:38,645 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-03-19 03:40:38,651 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=Craig_NestedInterpolation, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP [2022-03-19 03:40:38,652 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-03-19 03:40:38,663 INFO L276 IsEmpty]: Start isEmpty. Operand has 36 states, 16 states have (on average 1.375) internal successors, (22), 17 states have internal predecessors, (22), 14 states have call successors, (14), 4 states have call predecessors, (14), 4 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2022-03-19 03:40:38,670 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-03-19 03:40:38,670 INFO L492 BasicCegarLoop]: Found error trace [2022-03-19 03:40:38,670 INFO L500 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-19 03:40:38,671 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-19 03:40:38,678 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-19 03:40:38,678 INFO L85 PathProgramCache]: Analyzing trace with hash 503189915, now seen corresponding path program 1 times [2022-03-19 03:40:38,687 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-19 03:40:38,688 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [800730252] [2022-03-19 03:40:38,697 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-19 03:40:38,697 INFO L85 PathProgramCache]: Analyzing trace with hash 503189915, now seen corresponding path program 2 times [2022-03-19 03:40:38,699 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-19 03:40:38,699 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [256180189] [2022-03-19 03:40:38,700 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-19 03:40:38,701 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-19 03:40:38,774 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-19 03:40:38,828 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-19 03:40:38,832 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-19 03:40:38,841 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-19 03:40:38,843 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-19 03:40:38,848 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-19 03:40:38,849 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-19 03:40:38,849 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [256180189] [2022-03-19 03:40:38,850 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [256180189] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-19 03:40:38,850 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-19 03:40:38,850 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-19 03:40:38,852 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-19 03:40:38,852 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [800730252] [2022-03-19 03:40:38,852 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [800730252] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-19 03:40:38,853 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-19 03:40:38,853 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-19 03:40:38,853 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1797452281] [2022-03-19 03:40:38,853 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-19 03:40:38,857 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-03-19 03:40:38,857 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-19 03:40:38,877 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-03-19 03:40:38,877 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-19 03:40:38,879 INFO L87 Difference]: Start difference. First operand has 36 states, 16 states have (on average 1.375) internal successors, (22), 17 states have internal predecessors, (22), 14 states have call successors, (14), 4 states have call predecessors, (14), 4 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) Second operand has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-19 03:40:39,017 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-19 03:40:39,017 INFO L93 Difference]: Finished difference Result 63 states and 101 transitions. [2022-03-19 03:40:39,020 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-03-19 03:40:39,031 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2022-03-19 03:40:39,032 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-19 03:40:39,037 INFO L225 Difference]: With dead ends: 63 [2022-03-19 03:40:39,037 INFO L226 Difference]: Without dead ends: 31 [2022-03-19 03:40:39,039 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-19 03:40:39,042 INFO L912 BasicCegarLoop]: 34 mSDtfsCounter, 15 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 14 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 37 SdHoareTripleChecker+Invalid, 27 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 14 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-19 03:40:39,043 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [27 Valid, 37 Invalid, 27 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 14 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-19 03:40:39,056 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2022-03-19 03:40:39,080 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 31. [2022-03-19 03:40:39,081 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31 states, 13 states have (on average 1.1538461538461537) internal successors, (15), 14 states have internal predecessors, (15), 14 states have call successors, (14), 4 states have call predecessors, (14), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-03-19 03:40:39,083 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 41 transitions. [2022-03-19 03:40:39,084 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 41 transitions. Word has length 17 [2022-03-19 03:40:39,084 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-19 03:40:39,084 INFO L478 AbstractCegarLoop]: Abstraction has 31 states and 41 transitions. [2022-03-19 03:40:39,084 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-19 03:40:39,085 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 41 transitions. [2022-03-19 03:40:39,085 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-03-19 03:40:39,085 INFO L492 BasicCegarLoop]: Found error trace [2022-03-19 03:40:39,085 INFO L500 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-19 03:40:39,086 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-03-19 03:40:39,086 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-19 03:40:39,086 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-19 03:40:39,086 INFO L85 PathProgramCache]: Analyzing trace with hash 1171868123, now seen corresponding path program 1 times [2022-03-19 03:40:39,087 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-19 03:40:39,087 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [663458887] [2022-03-19 03:40:39,091 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-19 03:40:39,091 INFO L85 PathProgramCache]: Analyzing trace with hash 1171868123, now seen corresponding path program 2 times [2022-03-19 03:40:39,092 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-19 03:40:39,092 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1882212884] [2022-03-19 03:40:39,092 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-19 03:40:39,092 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-19 03:40:39,114 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-19 03:40:39,219 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-19 03:40:39,223 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-19 03:40:39,231 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-19 03:40:39,232 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-19 03:40:39,244 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-19 03:40:39,244 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-19 03:40:39,245 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1882212884] [2022-03-19 03:40:39,245 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1882212884] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-19 03:40:39,245 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-19 03:40:39,245 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-19 03:40:39,246 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-19 03:40:39,246 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [663458887] [2022-03-19 03:40:39,246 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [663458887] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-19 03:40:39,246 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-19 03:40:39,246 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-19 03:40:39,246 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [994605509] [2022-03-19 03:40:39,247 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-19 03:40:39,247 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-19 03:40:39,247 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-19 03:40:39,248 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-19 03:40:39,248 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-03-19 03:40:39,248 INFO L87 Difference]: Start difference. First operand 31 states and 41 transitions. Second operand has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-19 03:40:39,459 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-19 03:40:39,460 INFO L93 Difference]: Finished difference Result 37 states and 46 transitions. [2022-03-19 03:40:39,461 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-19 03:40:39,461 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2022-03-19 03:40:39,462 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-19 03:40:39,463 INFO L225 Difference]: With dead ends: 37 [2022-03-19 03:40:39,463 INFO L226 Difference]: Without dead ends: 35 [2022-03-19 03:40:39,464 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-03-19 03:40:39,465 INFO L912 BasicCegarLoop]: 26 mSDtfsCounter, 22 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 106 mSolverCounterSat, 37 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 43 SdHoareTripleChecker+Invalid, 143 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 37 IncrementalHoareTripleChecker+Valid, 106 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-19 03:40:39,465 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [23 Valid, 43 Invalid, 143 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [37 Valid, 106 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-19 03:40:39,467 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2022-03-19 03:40:39,476 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 35. [2022-03-19 03:40:39,476 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 16 states have (on average 1.125) internal successors, (18), 17 states have internal predecessors, (18), 14 states have call successors, (14), 5 states have call predecessors, (14), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-03-19 03:40:39,478 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 44 transitions. [2022-03-19 03:40:39,478 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 44 transitions. Word has length 17 [2022-03-19 03:40:39,478 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-19 03:40:39,478 INFO L478 AbstractCegarLoop]: Abstraction has 35 states and 44 transitions. [2022-03-19 03:40:39,478 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-19 03:40:39,479 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 44 transitions. [2022-03-19 03:40:39,479 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2022-03-19 03:40:39,479 INFO L492 BasicCegarLoop]: Found error trace [2022-03-19 03:40:39,479 INFO L500 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-19 03:40:39,480 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-03-19 03:40:39,480 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-19 03:40:39,480 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-19 03:40:39,481 INFO L85 PathProgramCache]: Analyzing trace with hash -1781524074, now seen corresponding path program 1 times [2022-03-19 03:40:39,481 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-19 03:40:39,481 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [729059937] [2022-03-19 03:40:39,482 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-19 03:40:39,482 INFO L85 PathProgramCache]: Analyzing trace with hash -1781524074, now seen corresponding path program 2 times [2022-03-19 03:40:39,482 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-19 03:40:39,482 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1711520897] [2022-03-19 03:40:39,483 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-19 03:40:39,483 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-19 03:40:39,505 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-19 03:40:39,506 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1736851327] [2022-03-19 03:40:39,506 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-19 03:40:39,506 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-19 03:40:39,506 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-19 03:40:39,511 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-19 03:40:39,520 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-03-19 03:40:39,571 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-19 03:40:39,572 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-19 03:40:39,584 INFO L263 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-19 03:40:39,597 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-19 03:40:39,742 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-19 03:40:39,743 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-19 03:40:39,743 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-19 03:40:39,744 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1711520897] [2022-03-19 03:40:39,744 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-19 03:40:39,744 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1736851327] [2022-03-19 03:40:39,744 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1736851327] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-19 03:40:39,744 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-19 03:40:39,745 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-19 03:40:39,745 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-19 03:40:39,745 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [729059937] [2022-03-19 03:40:39,746 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [729059937] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-19 03:40:39,747 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-19 03:40:39,747 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-19 03:40:39,747 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1286312193] [2022-03-19 03:40:39,747 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-19 03:40:39,748 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-19 03:40:39,748 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-19 03:40:39,748 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-19 03:40:39,748 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-19 03:40:39,749 INFO L87 Difference]: Start difference. First operand 35 states and 44 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-03-19 03:40:39,839 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-19 03:40:39,839 INFO L93 Difference]: Finished difference Result 54 states and 73 transitions. [2022-03-19 03:40:39,840 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-19 03:40:39,840 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 22 [2022-03-19 03:40:39,841 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-19 03:40:39,844 INFO L225 Difference]: With dead ends: 54 [2022-03-19 03:40:39,844 INFO L226 Difference]: Without dead ends: 52 [2022-03-19 03:40:39,845 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-03-19 03:40:39,852 INFO L912 BasicCegarLoop]: 49 mSDtfsCounter, 6 mSDsluCounter, 119 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 168 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-19 03:40:39,855 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [15 Valid, 168 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-19 03:40:39,856 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2022-03-19 03:40:39,875 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 42. [2022-03-19 03:40:39,876 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 42 states, 20 states have (on average 1.1) internal successors, (22), 22 states have internal predecessors, (22), 16 states have call successors, (16), 6 states have call predecessors, (16), 5 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2022-03-19 03:40:39,883 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 52 transitions. [2022-03-19 03:40:39,884 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 52 transitions. Word has length 22 [2022-03-19 03:40:39,884 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-19 03:40:39,884 INFO L478 AbstractCegarLoop]: Abstraction has 42 states and 52 transitions. [2022-03-19 03:40:39,884 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-03-19 03:40:39,885 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 52 transitions. [2022-03-19 03:40:39,885 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2022-03-19 03:40:39,885 INFO L492 BasicCegarLoop]: Found error trace [2022-03-19 03:40:39,885 INFO L500 BasicCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-19 03:40:39,914 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-03-19 03:40:40,108 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-19 03:40:40,109 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-19 03:40:40,109 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-19 03:40:40,109 INFO L85 PathProgramCache]: Analyzing trace with hash 1241120379, now seen corresponding path program 1 times [2022-03-19 03:40:40,110 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-19 03:40:40,110 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1506143126] [2022-03-19 03:40:40,110 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-19 03:40:40,111 INFO L85 PathProgramCache]: Analyzing trace with hash 1241120379, now seen corresponding path program 2 times [2022-03-19 03:40:40,111 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-19 03:40:40,111 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [690126191] [2022-03-19 03:40:40,111 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-19 03:40:40,111 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-19 03:40:40,121 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-19 03:40:40,121 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1892643028] [2022-03-19 03:40:40,122 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-19 03:40:40,122 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-19 03:40:40,122 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-19 03:40:40,123 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-19 03:40:40,138 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-03-19 03:40:40,165 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-19 03:40:40,166 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-19 03:40:40,167 INFO L263 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-19 03:40:40,168 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-19 03:40:40,310 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-19 03:40:40,310 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-19 03:40:40,310 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-19 03:40:40,311 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [690126191] [2022-03-19 03:40:40,311 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-19 03:40:40,311 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1892643028] [2022-03-19 03:40:40,312 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1892643028] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-19 03:40:40,312 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-19 03:40:40,312 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-19 03:40:40,312 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-19 03:40:40,313 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1506143126] [2022-03-19 03:40:40,313 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1506143126] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-19 03:40:40,313 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-19 03:40:40,313 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-19 03:40:40,313 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1916193273] [2022-03-19 03:40:40,313 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-19 03:40:40,314 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-19 03:40:40,315 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-19 03:40:40,317 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-19 03:40:40,318 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-19 03:40:40,323 INFO L87 Difference]: Start difference. First operand 42 states and 52 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-19 03:40:40,376 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-19 03:40:40,376 INFO L93 Difference]: Finished difference Result 58 states and 76 transitions. [2022-03-19 03:40:40,376 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-19 03:40:40,376 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 27 [2022-03-19 03:40:40,377 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-19 03:40:40,379 INFO L225 Difference]: With dead ends: 58 [2022-03-19 03:40:40,379 INFO L226 Difference]: Without dead ends: 56 [2022-03-19 03:40:40,381 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 27 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-03-19 03:40:40,385 INFO L912 BasicCegarLoop]: 48 mSDtfsCounter, 6 mSDsluCounter, 117 mSDsCounter, 0 mSdLazyCounter, 34 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 165 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 34 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-19 03:40:40,386 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 165 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 34 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-19 03:40:40,388 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2022-03-19 03:40:40,410 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 52. [2022-03-19 03:40:40,410 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 24 states have (on average 1.125) internal successors, (27), 26 states have internal predecessors, (27), 21 states have call successors, (21), 7 states have call predecessors, (21), 6 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) [2022-03-19 03:40:40,413 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 67 transitions. [2022-03-19 03:40:40,413 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 67 transitions. Word has length 27 [2022-03-19 03:40:40,413 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-19 03:40:40,414 INFO L478 AbstractCegarLoop]: Abstraction has 52 states and 67 transitions. [2022-03-19 03:40:40,414 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-19 03:40:40,414 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 67 transitions. [2022-03-19 03:40:40,415 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2022-03-19 03:40:40,415 INFO L492 BasicCegarLoop]: Found error trace [2022-03-19 03:40:40,415 INFO L500 BasicCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-19 03:40:40,441 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-03-19 03:40:40,635 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable3 [2022-03-19 03:40:40,636 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-19 03:40:40,636 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-19 03:40:40,636 INFO L85 PathProgramCache]: Analyzing trace with hash 1598126198, now seen corresponding path program 1 times [2022-03-19 03:40:40,636 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-19 03:40:40,636 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [990291161] [2022-03-19 03:40:40,637 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-19 03:40:40,637 INFO L85 PathProgramCache]: Analyzing trace with hash 1598126198, now seen corresponding path program 2 times [2022-03-19 03:40:40,637 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-19 03:40:40,637 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [16259615] [2022-03-19 03:40:40,638 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-19 03:40:40,638 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-19 03:40:40,649 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-19 03:40:40,649 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1728385503] [2022-03-19 03:40:40,649 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-19 03:40:40,649 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-19 03:40:40,650 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-19 03:40:40,652 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-19 03:40:40,670 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-03-19 03:40:40,693 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-19 03:40:40,693 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-19 03:40:40,694 INFO L263 TraceCheckSpWp]: Trace formula consists of 95 conjuncts, 9 conjunts are in the unsatisfiable core [2022-03-19 03:40:40,696 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-19 03:40:40,803 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-19 03:40:40,803 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-19 03:40:40,803 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-19 03:40:40,803 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [16259615] [2022-03-19 03:40:40,803 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-19 03:40:40,803 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1728385503] [2022-03-19 03:40:40,803 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1728385503] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-19 03:40:40,804 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-19 03:40:40,804 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-19 03:40:40,804 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-19 03:40:40,804 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [990291161] [2022-03-19 03:40:40,804 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [990291161] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-19 03:40:40,804 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-19 03:40:40,804 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-19 03:40:40,804 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1023481684] [2022-03-19 03:40:40,805 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-19 03:40:40,805 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-19 03:40:40,805 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-19 03:40:40,806 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-19 03:40:40,806 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-19 03:40:40,806 INFO L87 Difference]: Start difference. First operand 52 states and 67 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-03-19 03:40:40,882 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-19 03:40:40,882 INFO L93 Difference]: Finished difference Result 66 states and 82 transitions. [2022-03-19 03:40:40,882 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-19 03:40:40,883 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 32 [2022-03-19 03:40:40,883 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-19 03:40:40,884 INFO L225 Difference]: With dead ends: 66 [2022-03-19 03:40:40,885 INFO L226 Difference]: Without dead ends: 54 [2022-03-19 03:40:40,885 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-03-19 03:40:40,886 INFO L912 BasicCegarLoop]: 45 mSDtfsCounter, 6 mSDsluCounter, 112 mSDsCounter, 0 mSdLazyCounter, 42 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 157 SdHoareTripleChecker+Invalid, 48 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 42 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-19 03:40:40,886 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [13 Valid, 157 Invalid, 48 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 42 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-19 03:40:40,887 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2022-03-19 03:40:40,901 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2022-03-19 03:40:40,901 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 27 states have (on average 1.0740740740740742) internal successors, (29), 28 states have internal predecessors, (29), 19 states have call successors, (19), 8 states have call predecessors, (19), 7 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-03-19 03:40:40,905 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 65 transitions. [2022-03-19 03:40:40,905 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 65 transitions. Word has length 32 [2022-03-19 03:40:40,905 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-19 03:40:40,905 INFO L478 AbstractCegarLoop]: Abstraction has 54 states and 65 transitions. [2022-03-19 03:40:40,906 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-03-19 03:40:40,906 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 65 transitions. [2022-03-19 03:40:40,907 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2022-03-19 03:40:40,908 INFO L492 BasicCegarLoop]: Found error trace [2022-03-19 03:40:40,908 INFO L500 BasicCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-19 03:40:40,935 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-03-19 03:40:41,122 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-19 03:40:41,122 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-19 03:40:41,123 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-19 03:40:41,123 INFO L85 PathProgramCache]: Analyzing trace with hash 1002403483, now seen corresponding path program 1 times [2022-03-19 03:40:41,123 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-19 03:40:41,123 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [793859499] [2022-03-19 03:43:28,078 WARN L232 SmtUtils]: Spent 2.78m on a formula simplification. DAG size of input: 192 DAG size of output: 185 (called from [L 564] de.uni_freiburg.informatik.ultimate.icfgtransformer.loopacceleration.jordan.JordanLoopAcceleration.buildAccelerationFormula) [2022-03-19 03:43:28,088 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 0 HavocedVariables, 4 AssignedVariables, 0 ReadonlyVariables, Eigenvalues: {1={1=1, 4=1}}, 0 SequentialAcceleration, 1 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-19 03:43:28,090 INFO L271 tedInterpolationCore]: Starting analysis with loop acceleration approximation PRECISE [2022-03-19 03:43:28,092 INFO L85 PathProgramCache]: Analyzing trace with hash -1018400594, now seen corresponding path program 1 times [2022-03-19 03:43:28,093 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-19 03:43:28,093 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1510961525] [2022-03-19 03:43:28,093 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-19 03:43:28,093 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-19 03:43:28,104 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-19 03:43:28,104 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1684007649] [2022-03-19 03:43:28,104 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-19 03:43:28,104 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-19 03:43:28,104 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-19 03:43:28,108 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-19 03:43:28,109 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-03-19 03:43:28,383 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-19 03:43:28,384 INFO L263 TraceCheckSpWp]: Trace formula consists of 78 conjuncts, 17 conjunts are in the unsatisfiable core [2022-03-19 03:43:28,388 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-19 03:43:35,247 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-19 03:43:35,247 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-19 03:43:59,674 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-19 03:43:59,675 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-19 03:43:59,675 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1510961525] [2022-03-19 03:43:59,675 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-19 03:43:59,675 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1684007649] [2022-03-19 03:43:59,675 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1684007649] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-19 03:43:59,676 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-19 03:43:59,676 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 12 [2022-03-19 03:45:23,019 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-19 03:45:23,019 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [793859499] [2022-03-19 03:45:23,019 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [793859499] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-19 03:45:23,019 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-19 03:45:23,019 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [29] imperfect sequences [] total 29 [2022-03-19 03:45:23,019 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1882042011] [2022-03-19 03:45:23,019 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-19 03:45:23,020 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2022-03-19 03:45:23,020 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-19 03:45:23,020 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2022-03-19 03:45:23,021 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=191, Invalid=971, Unknown=28, NotChecked=0, Total=1190 [2022-03-19 03:45:23,021 INFO L87 Difference]: Start difference. First operand 54 states and 65 transitions. Second operand has 29 states, 23 states have (on average 1.3478260869565217) internal successors, (31), 17 states have internal predecessors, (31), 8 states have call successors, (10), 7 states have call predecessors, (10), 7 states have return successors, (8), 7 states have call predecessors, (8), 7 states have call successors, (8) [2022-03-19 03:45:33,873 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-19 03:45:33,873 INFO L93 Difference]: Finished difference Result 74 states and 83 transitions. [2022-03-19 03:45:33,873 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2022-03-19 03:45:33,874 INFO L78 Accepts]: Start accepts. Automaton has has 29 states, 23 states have (on average 1.3478260869565217) internal successors, (31), 17 states have internal predecessors, (31), 8 states have call successors, (10), 7 states have call predecessors, (10), 7 states have return successors, (8), 7 states have call predecessors, (8), 7 states have call successors, (8) Word has length 49 [2022-03-19 03:45:33,874 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-19 03:45:33,875 INFO L225 Difference]: With dead ends: 74 [2022-03-19 03:45:33,875 INFO L226 Difference]: Without dead ends: 72 [2022-03-19 03:45:33,875 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 86 GetRequests, 41 SyntacticMatches, 8 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 591 ImplicationChecksByTransitivity, 93.1s TimeCoverageRelationStatistics Valid=234, Invalid=1218, Unknown=30, NotChecked=0, Total=1482 [2022-03-19 03:45:33,876 INFO L912 BasicCegarLoop]: 32 mSDtfsCounter, 24 mSDsluCounter, 356 mSDsCounter, 0 mSdLazyCounter, 78 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 388 SdHoareTripleChecker+Invalid, 196 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 78 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 114 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2022-03-19 03:45:33,876 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 388 Invalid, 196 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 78 Invalid, 0 Unknown, 114 Unchecked, 0.7s Time] [2022-03-19 03:45:33,877 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2022-03-19 03:45:33,891 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 72. [2022-03-19 03:45:33,891 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 72 states, 41 states have (on average 1.0975609756097562) internal successors, (45), 41 states have internal predecessors, (45), 19 states have call successors, (19), 13 states have call predecessors, (19), 11 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-03-19 03:45:33,892 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 72 states to 72 states and 81 transitions. [2022-03-19 03:45:33,892 INFO L78 Accepts]: Start accepts. Automaton has 72 states and 81 transitions. Word has length 49 [2022-03-19 03:45:33,892 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-19 03:45:33,892 INFO L478 AbstractCegarLoop]: Abstraction has 72 states and 81 transitions. [2022-03-19 03:45:33,892 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 29 states, 23 states have (on average 1.3478260869565217) internal successors, (31), 17 states have internal predecessors, (31), 8 states have call successors, (10), 7 states have call predecessors, (10), 7 states have return successors, (8), 7 states have call predecessors, (8), 7 states have call successors, (8) [2022-03-19 03:45:33,893 INFO L276 IsEmpty]: Start isEmpty. Operand 72 states and 81 transitions. [2022-03-19 03:45:33,893 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2022-03-19 03:45:33,893 INFO L492 BasicCegarLoop]: Found error trace [2022-03-19 03:45:33,893 INFO L500 BasicCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-19 03:45:33,900 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-03-19 03:45:34,100 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-19 03:45:34,101 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-19 03:45:34,101 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-19 03:45:34,101 INFO L85 PathProgramCache]: Analyzing trace with hash -1130038122, now seen corresponding path program 2 times [2022-03-19 03:45:34,101 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-19 03:45:34,101 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1243464503] [2022-03-19 03:46:54,088 WARN L232 SmtUtils]: Spent 1.33m on a formula simplification. DAG size of input: 192 DAG size of output: 186 (called from [L 564] de.uni_freiburg.informatik.ultimate.icfgtransformer.loopacceleration.jordan.JordanLoopAcceleration.buildAccelerationFormula) [2022-03-19 03:46:54,093 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 0 HavocedVariables, 4 AssignedVariables, 0 ReadonlyVariables, Eigenvalues: {1={1=1, 4=1}}, 0 SequentialAcceleration, 1 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-19 03:46:54,094 INFO L271 tedInterpolationCore]: Starting analysis with loop acceleration approximation PRECISE [2022-03-19 03:46:54,095 INFO L85 PathProgramCache]: Analyzing trace with hash 1063970467, now seen corresponding path program 1 times [2022-03-19 03:46:54,095 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-19 03:46:54,095 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [688062314] [2022-03-19 03:46:54,095 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-19 03:46:54,095 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-19 03:46:54,104 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-19 03:46:54,104 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1721611201] [2022-03-19 03:46:54,104 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-19 03:46:54,104 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-19 03:46:54,104 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-19 03:46:54,112 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-19 03:46:54,112 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-03-19 03:46:54,838 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-03-19 03:46:54,838 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-03-19 03:46:54,986 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-03-19 03:46:55,004 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-03-19 03:46:55,004 INFO L85 PathProgramCache]: Analyzing trace with hash -1130038122, now seen corresponding path program 3 times [2022-03-19 03:46:55,005 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-19 03:46:55,005 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [865098758] [2022-03-19 03:46:55,005 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-19 03:46:55,005 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-19 03:46:55,013 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-19 03:46:55,013 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2003951892] [2022-03-19 03:46:55,013 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-03-19 03:46:55,013 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-19 03:46:55,013 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-19 03:46:55,047 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-19 03:46:55,115 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-03-19 03:46:55,127 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2022-03-19 03:46:55,127 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-19 03:46:55,128 INFO L263 TraceCheckSpWp]: Trace formula consists of 96 conjuncts, 13 conjunts are in the unsatisfiable core [2022-03-19 03:46:55,130 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-19 03:46:56,112 INFO L134 CoverageAnalysis]: Checked inductivity of 102 backedges. 14 proven. 4 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2022-03-19 03:46:56,112 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-19 03:46:56,720 INFO L134 CoverageAnalysis]: Checked inductivity of 102 backedges. 14 proven. 4 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2022-03-19 03:46:56,720 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-19 03:46:56,720 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [865098758] [2022-03-19 03:46:56,720 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-19 03:46:56,721 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2003951892] [2022-03-19 03:46:56,721 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2003951892] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-19 03:46:56,721 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-19 03:46:56,721 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2022-03-19 03:46:56,721 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-19 03:46:56,721 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1243464503] [2022-03-19 03:46:56,721 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1243464503] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-19 03:46:56,721 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-19 03:46:56,721 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-19 03:46:56,721 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [202315662] [2022-03-19 03:46:56,722 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-19 03:46:56,722 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-19 03:46:56,722 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-19 03:46:56,722 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-19 03:46:56,722 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2022-03-19 03:46:56,723 INFO L87 Difference]: Start difference. First operand 72 states and 81 transitions. Second operand has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2022-03-19 03:46:57,488 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-19 03:46:57,489 INFO L93 Difference]: Finished difference Result 91 states and 110 transitions. [2022-03-19 03:46:57,489 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-03-19 03:46:57,489 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) Word has length 54 [2022-03-19 03:46:57,490 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-19 03:46:57,491 INFO L225 Difference]: With dead ends: 91 [2022-03-19 03:46:57,491 INFO L226 Difference]: Without dead ends: 89 [2022-03-19 03:46:57,491 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 108 GetRequests, 100 SyntacticMatches, 1 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=20, Invalid=52, Unknown=0, NotChecked=0, Total=72 [2022-03-19 03:46:57,491 INFO L912 BasicCegarLoop]: 58 mSDtfsCounter, 6 mSDsluCounter, 180 mSDsCounter, 0 mSdLazyCounter, 65 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 238 SdHoareTripleChecker+Invalid, 67 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 65 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2022-03-19 03:46:57,492 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 238 Invalid, 67 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 65 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2022-03-19 03:46:57,492 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states. [2022-03-19 03:46:57,516 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 80. [2022-03-19 03:46:57,516 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 80 states, 45 states have (on average 1.0888888888888888) internal successors, (49), 46 states have internal predecessors, (49), 22 states have call successors, (22), 14 states have call predecessors, (22), 12 states have return successors, (20), 19 states have call predecessors, (20), 20 states have call successors, (20) [2022-03-19 03:46:57,518 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 80 states to 80 states and 91 transitions. [2022-03-19 03:46:57,519 INFO L78 Accepts]: Start accepts. Automaton has 80 states and 91 transitions. Word has length 54 [2022-03-19 03:46:57,519 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-19 03:46:57,519 INFO L478 AbstractCegarLoop]: Abstraction has 80 states and 91 transitions. [2022-03-19 03:46:57,519 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2022-03-19 03:46:57,520 INFO L276 IsEmpty]: Start isEmpty. Operand 80 states and 91 transitions. [2022-03-19 03:46:57,521 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2022-03-19 03:46:57,521 INFO L492 BasicCegarLoop]: Found error trace [2022-03-19 03:46:57,521 INFO L500 BasicCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-19 03:46:57,530 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2022-03-19 03:46:57,739 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-03-19 03:46:57,924 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-19 03:46:57,924 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-19 03:46:57,924 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-19 03:46:57,924 INFO L85 PathProgramCache]: Analyzing trace with hash -1546120389, now seen corresponding path program 4 times [2022-03-19 03:46:57,924 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-19 03:46:57,924 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [502560316] [2022-03-19 03:48:24,455 WARN L232 SmtUtils]: Spent 1.44m on a formula simplification. DAG size of input: 192 DAG size of output: 186 (called from [L 564] de.uni_freiburg.informatik.ultimate.icfgtransformer.loopacceleration.jordan.JordanLoopAcceleration.buildAccelerationFormula) [2022-03-19 03:48:24,458 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 0 HavocedVariables, 4 AssignedVariables, 0 ReadonlyVariables, Eigenvalues: {1={1=1, 4=1}}, 0 SequentialAcceleration, 1 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-19 03:48:24,459 INFO L271 tedInterpolationCore]: Starting analysis with loop acceleration approximation PRECISE [2022-03-19 03:48:24,460 INFO L85 PathProgramCache]: Analyzing trace with hash 1624834318, now seen corresponding path program 1 times [2022-03-19 03:48:24,460 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-19 03:48:24,460 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [258163506] [2022-03-19 03:48:24,461 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-19 03:48:24,461 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-19 03:48:24,468 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-19 03:48:24,469 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [102864161] [2022-03-19 03:48:24,469 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-19 03:48:24,469 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-19 03:48:24,469 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-19 03:48:24,471 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-19 03:48:24,477 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-03-19 03:48:24,934 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-19 03:48:24,936 INFO L263 TraceCheckSpWp]: Trace formula consists of 96 conjuncts, 27 conjunts are in the unsatisfiable core [2022-03-19 03:48:24,938 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-19 03:48:33,740 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 3 proven. 3 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-19 03:48:33,740 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-19 03:48:37,529 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 3 proven. 3 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-19 03:48:37,529 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-19 03:48:37,529 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [258163506] [2022-03-19 03:48:37,529 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-19 03:48:37,529 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [102864161] [2022-03-19 03:48:37,529 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [102864161] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-19 03:48:37,530 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-19 03:48:37,530 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 13 [2022-03-19 03:50:11,550 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-19 03:50:11,550 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [502560316] [2022-03-19 03:50:11,551 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [502560316] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-19 03:50:11,551 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-19 03:50:11,551 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [29] imperfect sequences [] total 29 [2022-03-19 03:50:11,551 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2051057043] [2022-03-19 03:50:11,551 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-19 03:50:11,551 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2022-03-19 03:50:11,551 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-19 03:50:11,552 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2022-03-19 03:50:11,552 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=197, Invalid=1035, Unknown=28, NotChecked=0, Total=1260 [2022-03-19 03:50:11,553 INFO L87 Difference]: Start difference. First operand 80 states and 91 transitions. Second operand has 29 states, 23 states have (on average 1.3478260869565217) internal successors, (31), 17 states have internal predecessors, (31), 8 states have call successors, (12), 7 states have call predecessors, (12), 7 states have return successors, (10), 8 states have call predecessors, (10), 7 states have call successors, (10) [2022-03-19 03:50:33,070 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-19 03:50:33,070 INFO L93 Difference]: Finished difference Result 94 states and 103 transitions. [2022-03-19 03:50:33,071 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2022-03-19 03:50:33,071 INFO L78 Accepts]: Start accepts. Automaton has has 29 states, 23 states have (on average 1.3478260869565217) internal successors, (31), 17 states have internal predecessors, (31), 8 states have call successors, (12), 7 states have call predecessors, (12), 7 states have return successors, (10), 8 states have call predecessors, (10), 7 states have call successors, (10) Word has length 59 [2022-03-19 03:50:33,071 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-19 03:50:33,073 INFO L225 Difference]: With dead ends: 94 [2022-03-19 03:50:33,074 INFO L226 Difference]: Without dead ends: 92 [2022-03-19 03:50:33,074 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 107 GetRequests, 59 SyntacticMatches, 8 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 710 ImplicationChecksByTransitivity, 117.7s TimeCoverageRelationStatistics Valid=264, Invalid=1428, Unknown=30, NotChecked=0, Total=1722 [2022-03-19 03:50:33,075 INFO L912 BasicCegarLoop]: 32 mSDtfsCounter, 25 mSDsluCounter, 396 mSDsCounter, 0 mSdLazyCounter, 75 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 428 SdHoareTripleChecker+Invalid, 247 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 75 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 157 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2022-03-19 03:50:33,075 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [26 Valid, 428 Invalid, 247 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 75 Invalid, 0 Unknown, 157 Unchecked, 0.8s Time] [2022-03-19 03:50:33,075 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2022-03-19 03:50:33,110 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 92. [2022-03-19 03:50:33,111 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 92 states, 54 states have (on average 1.0740740740740742) internal successors, (58), 55 states have internal predecessors, (58), 22 states have call successors, (22), 17 states have call predecessors, (22), 15 states have return successors, (20), 19 states have call predecessors, (20), 20 states have call successors, (20) [2022-03-19 03:50:33,111 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 92 states to 92 states and 100 transitions. [2022-03-19 03:50:33,111 INFO L78 Accepts]: Start accepts. Automaton has 92 states and 100 transitions. Word has length 59 [2022-03-19 03:50:33,112 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-19 03:50:33,112 INFO L478 AbstractCegarLoop]: Abstraction has 92 states and 100 transitions. [2022-03-19 03:50:33,112 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 29 states, 23 states have (on average 1.3478260869565217) internal successors, (31), 17 states have internal predecessors, (31), 8 states have call successors, (12), 7 states have call predecessors, (12), 7 states have return successors, (10), 8 states have call predecessors, (10), 7 states have call successors, (10) [2022-03-19 03:50:33,112 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states and 100 transitions. [2022-03-19 03:50:33,113 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2022-03-19 03:50:33,113 INFO L492 BasicCegarLoop]: Found error trace [2022-03-19 03:50:33,113 INFO L500 BasicCegarLoop]: trace histogram [10, 9, 9, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-19 03:50:33,123 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2022-03-19 03:50:33,322 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-19 03:50:33,323 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-19 03:50:33,323 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-19 03:50:33,323 INFO L85 PathProgramCache]: Analyzing trace with hash -389057674, now seen corresponding path program 5 times [2022-03-19 03:50:33,323 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-19 03:50:33,323 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [433847280] [2022-03-19 03:53:10,757 WARN L232 SmtUtils]: Spent 2.62m on a formula simplification. DAG size of input: 195 DAG size of output: 188 (called from [L 564] de.uni_freiburg.informatik.ultimate.icfgtransformer.loopacceleration.jordan.JordanLoopAcceleration.buildAccelerationFormula) [2022-03-19 03:53:10,759 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 0 HavocedVariables, 4 AssignedVariables, 0 ReadonlyVariables, Eigenvalues: {1={1=1, 4=1}}, 0 SequentialAcceleration, 1 AlternatingAcceleration, 0 QuantifierFreeResult [2022-03-19 03:53:10,760 INFO L271 tedInterpolationCore]: Starting analysis with loop acceleration approximation PRECISE [2022-03-19 03:53:10,761 INFO L85 PathProgramCache]: Analyzing trace with hash 746353091, now seen corresponding path program 1 times [2022-03-19 03:53:10,761 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-19 03:53:10,761 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1976443087] [2022-03-19 03:53:10,761 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-19 03:53:10,761 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-19 03:53:10,773 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-19 03:53:10,773 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [75286765] [2022-03-19 03:53:10,773 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-19 03:53:10,774 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-19 03:53:10,774 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-19 03:53:10,775 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-19 03:53:10,775 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-03-19 03:53:11,109 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-19 03:53:11,111 INFO L263 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 22 conjunts are in the unsatisfiable core [2022-03-19 03:53:11,113 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-19 03:54:26,897 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 6 proven. 14 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-19 03:54:26,897 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-19 03:54:29,173 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 6 proven. 14 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-19 03:54:29,174 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-19 03:54:29,174 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1976443087] [2022-03-19 03:54:29,174 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-19 03:54:29,174 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [75286765] [2022-03-19 03:54:29,174 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [75286765] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-19 03:54:29,174 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-19 03:54:29,174 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 13