/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_valuebound50.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-34549b5 [2022-04-06 15:40:04,875 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-06 15:40:04,877 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-06 15:40:04,929 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-06 15:40:04,929 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-06 15:40:04,931 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-06 15:40:04,934 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-06 15:40:04,940 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-06 15:40:04,941 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-06 15:40:04,946 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-06 15:40:04,947 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-06 15:40:04,949 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-06 15:40:04,949 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-06 15:40:04,951 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-06 15:40:04,953 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-06 15:40:04,956 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-06 15:40:04,957 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-06 15:40:04,959 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-06 15:40:04,961 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-06 15:40:04,968 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-06 15:40:04,969 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-06 15:40:04,971 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-06 15:40:04,972 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-06 15:40:04,973 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-06 15:40:04,974 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-06 15:40:04,976 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-06 15:40:04,976 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-06 15:40:04,977 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-06 15:40:04,978 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-06 15:40:04,978 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-06 15:40:04,980 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-06 15:40:04,980 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-06 15:40:04,982 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-06 15:40:04,982 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-06 15:40:04,983 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-06 15:40:04,984 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-06 15:40:04,984 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-06 15:40:04,984 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-06 15:40:04,985 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-06 15:40:04,985 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-06 15:40:04,986 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-06 15:40:04,987 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-06 15:40:04,988 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationJordan_32.epf [2022-04-06 15:40:05,004 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-06 15:40:05,004 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-06 15:40:05,005 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-06 15:40:05,006 INFO L138 SettingsManager]: * sizeof long=4 [2022-04-06 15:40:05,006 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-06 15:40:05,006 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-04-06 15:40:05,006 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-06 15:40:05,006 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-06 15:40:05,006 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-06 15:40:05,007 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-06 15:40:05,008 INFO L138 SettingsManager]: * sizeof long double=12 [2022-04-06 15:40:05,008 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-06 15:40:05,008 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-06 15:40:05,008 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-06 15:40:05,008 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-06 15:40:05,008 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-06 15:40:05,008 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-06 15:40:05,008 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-06 15:40:05,008 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-06 15:40:05,009 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-06 15:40:05,009 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-04-06 15:40:05,009 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-04-06 15:40:05,009 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-04-06 15:40:05,009 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-06 15:40:05,009 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=JORDAN [2022-04-06 15:40:05,009 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-04-06 15:40:05,228 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-06 15:40:05,257 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-06 15:40:05,259 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-06 15:40:05,260 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-06 15:40:05,261 INFO L275 PluginConnector]: CDTParser initialized [2022-04-06 15:40:05,263 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/cohencu-ll_valuebound50.c [2022-04-06 15:40:05,320 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3b38db83d/d24619b433ce4b5a875e7edf4ff30a7f/FLAGcd5f03730 [2022-04-06 15:40:05,773 INFO L306 CDTParser]: Found 1 translation units. [2022-04-06 15:40:05,774 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/cohencu-ll_valuebound50.c [2022-04-06 15:40:05,782 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3b38db83d/d24619b433ce4b5a875e7edf4ff30a7f/FLAGcd5f03730 [2022-04-06 15:40:05,795 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3b38db83d/d24619b433ce4b5a875e7edf4ff30a7f [2022-04-06 15:40:05,797 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-06 15:40:05,798 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-06 15:40:05,801 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-06 15:40:05,802 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-06 15:40:05,804 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-06 15:40:05,805 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 03:40:05" (1/1) ... [2022-04-06 15:40:05,806 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4c67194c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 03:40:05, skipping insertion in model container [2022-04-06 15:40:05,806 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 03:40:05" (1/1) ... [2022-04-06 15:40:05,812 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-06 15:40:05,828 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-06 15:40:06,009 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_valuebound50.c[588,601] [2022-04-06 15:40:06,054 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-06 15:40:06,062 INFO L203 MainTranslator]: Completed pre-run [2022-04-06 15:40:06,079 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_valuebound50.c[588,601] [2022-04-06 15:40:06,103 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-06 15:40:06,122 INFO L208 MainTranslator]: Completed translation [2022-04-06 15:40:06,123 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 03:40:06 WrapperNode [2022-04-06 15:40:06,124 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-06 15:40:06,126 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-06 15:40:06,126 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-06 15:40:06,126 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-06 15:40:06,136 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 03:40:06" (1/1) ... [2022-04-06 15:40:06,136 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 03:40:06" (1/1) ... [2022-04-06 15:40:06,153 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 03:40:06" (1/1) ... [2022-04-06 15:40:06,153 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 03:40:06" (1/1) ... [2022-04-06 15:40:06,157 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 03:40:06" (1/1) ... [2022-04-06 15:40:06,161 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 03:40:06" (1/1) ... [2022-04-06 15:40:06,162 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 03:40:06" (1/1) ... [2022-04-06 15:40:06,169 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-06 15:40:06,171 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-06 15:40:06,171 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-06 15:40:06,171 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-06 15:40:06,172 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 03:40:06" (1/1) ... [2022-04-06 15:40:06,179 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-06 15:40:06,190 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 15:40:06,210 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-04-06 15:40:06,229 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-04-06 15:40:06,257 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-06 15:40:06,258 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-06 15:40:06,258 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-06 15:40:06,259 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-06 15:40:06,259 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-06 15:40:06,259 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-06 15:40:06,259 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-06 15:40:06,259 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-06 15:40:06,259 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-06 15:40:06,259 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-06 15:40:06,260 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_ushort [2022-04-06 15:40:06,260 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-06 15:40:06,261 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-06 15:40:06,261 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-06 15:40:06,261 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-06 15:40:06,261 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-06 15:40:06,261 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-06 15:40:06,262 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-06 15:40:06,262 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-06 15:40:06,262 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-06 15:40:06,321 INFO L234 CfgBuilder]: Building ICFG [2022-04-06 15:40:06,323 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-06 15:40:06,479 INFO L275 CfgBuilder]: Performing block encoding [2022-04-06 15:40:06,484 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-06 15:40:06,484 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-04-06 15:40:06,486 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 03:40:06 BoogieIcfgContainer [2022-04-06 15:40:06,486 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-06 15:40:06,488 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-06 15:40:06,488 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-06 15:40:06,491 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-06 15:40:06,491 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 06.04 03:40:05" (1/3) ... [2022-04-06 15:40:06,492 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@66a5438 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 03:40:06, skipping insertion in model container [2022-04-06 15:40:06,492 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 03:40:06" (2/3) ... [2022-04-06 15:40:06,492 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@66a5438 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 03:40:06, skipping insertion in model container [2022-04-06 15:40:06,492 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 03:40:06" (3/3) ... [2022-04-06 15:40:06,494 INFO L111 eAbstractionObserver]: Analyzing ICFG cohencu-ll_valuebound50.c [2022-04-06 15:40:06,498 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-04-06 15:40:06,499 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-06 15:40:06,536 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-06 15:40:06,542 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-04-06 15:40:06,543 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-06 15:40:06,555 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-04-06 15:40:06,562 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-04-06 15:40:06,562 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 15:40:06,563 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 15:40:06,564 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 15:40:06,583 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 15:40:06,583 INFO L85 PathProgramCache]: Analyzing trace with hash 503189915, now seen corresponding path program 1 times [2022-04-06 15:40:06,594 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 15:40:06,594 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [157430492] [2022-04-06 15:40:06,606 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 15:40:06,606 INFO L85 PathProgramCache]: Analyzing trace with hash 503189915, now seen corresponding path program 2 times [2022-04-06 15:40:06,608 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 15:40:06,609 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1445147551] [2022-04-06 15:40:06,609 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 15:40:06,611 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 15:40:06,722 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 15:40:06,793 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-06 15:40:06,804 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 15:40:06,819 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-06 15:40:06,822 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 15:40:06,836 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 15:40:06,836 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 15:40:06,837 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1445147551] [2022-04-06 15:40:06,837 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1445147551] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 15:40:06,838 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 15:40:06,838 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-06 15:40:06,840 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 15:40:06,841 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [157430492] [2022-04-06 15:40:06,841 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [157430492] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 15:40:06,841 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 15:40:06,841 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-06 15:40:06,841 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1075002516] [2022-04-06 15:40:06,842 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 15:40:06,846 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-06 15:40:06,846 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 15:40:06,876 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-06 15:40:06,877 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-06 15:40:06,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-04-06 15:40:06,986 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 15:40:06,986 INFO L93 Difference]: Finished difference Result 63 states and 101 transitions. [2022-04-06 15:40:06,990 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-06 15:40:06,992 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-04-06 15:40:06,992 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 15:40:06,998 INFO L225 Difference]: With dead ends: 63 [2022-04-06 15:40:06,998 INFO L226 Difference]: Without dead ends: 31 [2022-04-06 15:40:07,001 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-06 15:40:07,005 INFO L913 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-04-06 15:40:07,006 INFO L914 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-04-06 15:40:07,021 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2022-04-06 15:40:07,042 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 31. [2022-04-06 15:40:07,043 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-04-06 15:40:07,045 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 41 transitions. [2022-04-06 15:40:07,047 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 41 transitions. Word has length 17 [2022-04-06 15:40:07,047 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 15:40:07,047 INFO L478 AbstractCegarLoop]: Abstraction has 31 states and 41 transitions. [2022-04-06 15:40:07,048 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-04-06 15:40:07,048 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 41 transitions. [2022-04-06 15:40:07,048 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-04-06 15:40:07,048 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 15:40:07,049 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 15:40:07,049 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-06 15:40:07,049 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 15:40:07,050 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 15:40:07,050 INFO L85 PathProgramCache]: Analyzing trace with hash 1171868123, now seen corresponding path program 1 times [2022-04-06 15:40:07,050 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 15:40:07,050 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [928167805] [2022-04-06 15:40:07,051 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 15:40:07,051 INFO L85 PathProgramCache]: Analyzing trace with hash 1171868123, now seen corresponding path program 2 times [2022-04-06 15:40:07,052 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 15:40:07,052 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2116577139] [2022-04-06 15:40:07,052 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 15:40:07,052 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 15:40:07,070 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 15:40:07,210 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-06 15:40:07,212 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 15:40:07,222 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-06 15:40:07,224 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 15:40:07,231 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 15:40:07,231 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 15:40:07,232 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2116577139] [2022-04-06 15:40:07,232 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2116577139] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 15:40:07,232 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 15:40:07,232 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 15:40:07,233 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 15:40:07,233 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [928167805] [2022-04-06 15:40:07,233 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [928167805] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 15:40:07,233 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 15:40:07,233 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 15:40:07,233 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1555437600] [2022-04-06 15:40:07,234 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 15:40:07,234 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-06 15:40:07,234 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 15:40:07,235 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-06 15:40:07,235 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-04-06 15:40:07,235 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-04-06 15:40:07,455 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 15:40:07,456 INFO L93 Difference]: Finished difference Result 37 states and 46 transitions. [2022-04-06 15:40:07,459 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-06 15:40:07,459 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-04-06 15:40:07,462 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 15:40:07,463 INFO L225 Difference]: With dead ends: 37 [2022-04-06 15:40:07,463 INFO L226 Difference]: Without dead ends: 35 [2022-04-06 15:40:07,464 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-04-06 15:40:07,465 INFO L913 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.1s IncrementalHoareTripleChecker+Time [2022-04-06 15:40:07,468 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [23 Valid, 43 Invalid, 143 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [37 Valid, 106 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 15:40:07,472 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2022-04-06 15:40:07,480 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 35. [2022-04-06 15:40:07,481 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-04-06 15:40:07,482 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 44 transitions. [2022-04-06 15:40:07,482 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 44 transitions. Word has length 17 [2022-04-06 15:40:07,483 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 15:40:07,483 INFO L478 AbstractCegarLoop]: Abstraction has 35 states and 44 transitions. [2022-04-06 15:40:07,485 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-04-06 15:40:07,486 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 44 transitions. [2022-04-06 15:40:07,486 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2022-04-06 15:40:07,487 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 15:40:07,487 INFO L499 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-04-06 15:40:07,487 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-04-06 15:40:07,488 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 15:40:07,488 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 15:40:07,488 INFO L85 PathProgramCache]: Analyzing trace with hash -1781524074, now seen corresponding path program 1 times [2022-04-06 15:40:07,488 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 15:40:07,492 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [841423750] [2022-04-06 15:40:07,493 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 15:40:07,493 INFO L85 PathProgramCache]: Analyzing trace with hash -1781524074, now seen corresponding path program 2 times [2022-04-06 15:40:07,493 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 15:40:07,493 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1724563289] [2022-04-06 15:40:07,493 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 15:40:07,494 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 15:40:07,506 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 15:40:07,506 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1448498788] [2022-04-06 15:40:07,506 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 15:40:07,506 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 15:40:07,507 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 15:40:07,508 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 15:40:07,541 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-04-06 15:40:07,566 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 15:40:07,567 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 15:40:07,568 INFO L263 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-06 15:40:07,574 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 15:40:07,711 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 15:40:07,711 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 15:40:07,712 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 15:40:07,712 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1724563289] [2022-04-06 15:40:07,712 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 15:40:07,712 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1448498788] [2022-04-06 15:40:07,712 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1448498788] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 15:40:07,712 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 15:40:07,713 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 15:40:07,714 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 15:40:07,714 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [841423750] [2022-04-06 15:40:07,714 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [841423750] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 15:40:07,714 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 15:40:07,714 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 15:40:07,714 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2127926923] [2022-04-06 15:40:07,714 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 15:40:07,715 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 15:40:07,715 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 15:40:07,715 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 15:40:07,716 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-06 15:40:07,716 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-04-06 15:40:07,794 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 15:40:07,794 INFO L93 Difference]: Finished difference Result 54 states and 73 transitions. [2022-04-06 15:40:07,794 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 15:40:07,795 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-04-06 15:40:07,795 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 15:40:07,796 INFO L225 Difference]: With dead ends: 54 [2022-04-06 15:40:07,796 INFO L226 Difference]: Without dead ends: 52 [2022-04-06 15:40:07,797 INFO L912 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-04-06 15:40:07,798 INFO L913 BasicCegarLoop]: 49 mSDtfsCounter, 6 mSDsluCounter, 99 mSDsCounter, 0 mSdLazyCounter, 51 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 148 SdHoareTripleChecker+Invalid, 51 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 51 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 15:40:07,798 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [15 Valid, 148 Invalid, 51 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 51 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 15:40:07,799 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2022-04-06 15:40:07,809 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 42. [2022-04-06 15:40:07,809 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-04-06 15:40:07,810 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 52 transitions. [2022-04-06 15:40:07,810 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 52 transitions. Word has length 22 [2022-04-06 15:40:07,811 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 15:40:07,811 INFO L478 AbstractCegarLoop]: Abstraction has 42 states and 52 transitions. [2022-04-06 15:40:07,811 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-04-06 15:40:07,811 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 52 transitions. [2022-04-06 15:40:07,812 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2022-04-06 15:40:07,812 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 15:40:07,823 INFO L499 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-04-06 15:40:07,851 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2022-04-06 15:40:08,046 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-04-06 15:40:08,047 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 15:40:08,047 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 15:40:08,047 INFO L85 PathProgramCache]: Analyzing trace with hash 1241120379, now seen corresponding path program 1 times [2022-04-06 15:40:08,047 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 15:40:08,048 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1974013552] [2022-04-06 15:40:08,048 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 15:40:08,048 INFO L85 PathProgramCache]: Analyzing trace with hash 1241120379, now seen corresponding path program 2 times [2022-04-06 15:40:08,049 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 15:40:08,049 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1853781133] [2022-04-06 15:40:08,049 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 15:40:08,049 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 15:40:08,070 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 15:40:08,071 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [138054660] [2022-04-06 15:40:08,071 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 15:40:08,071 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 15:40:08,071 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 15:40:08,077 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 15:40:08,079 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-04-06 15:40:08,116 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 15:40:08,117 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 15:40:08,118 INFO L263 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-06 15:40:08,120 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 15:40:08,192 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-06 15:40:08,192 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 15:40:08,192 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 15:40:08,192 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1853781133] [2022-04-06 15:40:08,193 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 15:40:08,193 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [138054660] [2022-04-06 15:40:08,193 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [138054660] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 15:40:08,193 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 15:40:08,193 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 15:40:08,194 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 15:40:08,194 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1974013552] [2022-04-06 15:40:08,194 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1974013552] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 15:40:08,194 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 15:40:08,194 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 15:40:08,194 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1815607661] [2022-04-06 15:40:08,195 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 15:40:08,195 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 15:40:08,195 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 15:40:08,196 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 15:40:08,196 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-06 15:40:08,196 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-04-06 15:40:08,250 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 15:40:08,250 INFO L93 Difference]: Finished difference Result 58 states and 76 transitions. [2022-04-06 15:40:08,251 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 15:40:08,251 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-04-06 15:40:08,251 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 15:40:08,252 INFO L225 Difference]: With dead ends: 58 [2022-04-06 15:40:08,252 INFO L226 Difference]: Without dead ends: 56 [2022-04-06 15:40:08,253 INFO L912 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-04-06 15:40:08,253 INFO L913 BasicCegarLoop]: 48 mSDtfsCounter, 6 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 149 SdHoareTripleChecker+Invalid, 51 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 15:40:08,254 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 149 Invalid, 51 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 15:40:08,254 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2022-04-06 15:40:08,287 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 52. [2022-04-06 15:40:08,288 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-04-06 15:40:08,289 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 67 transitions. [2022-04-06 15:40:08,289 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 67 transitions. Word has length 27 [2022-04-06 15:40:08,290 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 15:40:08,290 INFO L478 AbstractCegarLoop]: Abstraction has 52 states and 67 transitions. [2022-04-06 15:40:08,290 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-04-06 15:40:08,290 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 67 transitions. [2022-04-06 15:40:08,291 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2022-04-06 15:40:08,291 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 15:40:08,291 INFO L499 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-04-06 15:40:08,317 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-04-06 15:40:08,499 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-04-06 15:40:08,500 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 15:40:08,500 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 15:40:08,500 INFO L85 PathProgramCache]: Analyzing trace with hash 1598126198, now seen corresponding path program 1 times [2022-04-06 15:40:08,500 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 15:40:08,501 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [824708413] [2022-04-06 15:40:08,501 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 15:40:08,501 INFO L85 PathProgramCache]: Analyzing trace with hash 1598126198, now seen corresponding path program 2 times [2022-04-06 15:40:08,501 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 15:40:08,501 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [229082027] [2022-04-06 15:40:08,501 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 15:40:08,502 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 15:40:08,511 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 15:40:08,512 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1875670046] [2022-04-06 15:40:08,512 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 15:40:08,512 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 15:40:08,512 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 15:40:08,513 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 15:40:08,521 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-04-06 15:40:08,558 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 15:40:08,558 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 15:40:08,559 INFO L263 TraceCheckSpWp]: Trace formula consists of 95 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-06 15:40:08,561 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 15:40:08,704 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-06 15:40:08,705 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 15:40:08,705 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 15:40:08,705 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [229082027] [2022-04-06 15:40:08,705 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 15:40:08,706 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1875670046] [2022-04-06 15:40:08,706 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1875670046] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 15:40:08,706 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 15:40:08,706 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 15:40:08,706 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 15:40:08,710 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [824708413] [2022-04-06 15:40:08,713 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [824708413] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 15:40:08,714 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 15:40:08,714 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 15:40:08,714 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [178738643] [2022-04-06 15:40:08,714 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 15:40:08,715 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 15:40:08,715 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 15:40:08,715 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 15:40:08,716 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-06 15:40:08,716 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-04-06 15:40:08,812 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 15:40:08,812 INFO L93 Difference]: Finished difference Result 66 states and 82 transitions. [2022-04-06 15:40:08,812 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 15:40:08,812 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-04-06 15:40:08,813 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 15:40:08,814 INFO L225 Difference]: With dead ends: 66 [2022-04-06 15:40:08,814 INFO L226 Difference]: Without dead ends: 54 [2022-04-06 15:40:08,814 INFO L912 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-04-06 15:40:08,815 INFO L913 BasicCegarLoop]: 45 mSDtfsCounter, 6 mSDsluCounter, 90 mSDsCounter, 0 mSdLazyCounter, 64 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 135 SdHoareTripleChecker+Invalid, 70 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 64 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 15:40:08,815 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [13 Valid, 135 Invalid, 70 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 64 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 15:40:08,816 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2022-04-06 15:40:08,826 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2022-04-06 15:40:08,827 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-04-06 15:40:08,828 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 65 transitions. [2022-04-06 15:40:08,828 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 65 transitions. Word has length 32 [2022-04-06 15:40:08,828 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 15:40:08,828 INFO L478 AbstractCegarLoop]: Abstraction has 54 states and 65 transitions. [2022-04-06 15:40:08,828 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-04-06 15:40:08,828 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 65 transitions. [2022-04-06 15:40:08,829 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2022-04-06 15:40:08,829 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 15:40:08,829 INFO L499 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-04-06 15:40:08,860 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-04-06 15:40:09,051 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-04-06 15:40:09,052 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 15:40:09,052 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 15:40:09,052 INFO L85 PathProgramCache]: Analyzing trace with hash 1002403483, now seen corresponding path program 1 times [2022-04-06 15:40:09,052 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 15:40:09,052 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [456579806] [2022-04-06 15:41:34,526 WARN L232 SmtUtils]: Spent 1.42m 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-04-06 15:41:34,534 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-04-06 15:41:34,542 INFO L271 tedInterpolationCore]: Starting analysis with loop acceleration approximation PRECISE [2022-04-06 15:41:34,545 INFO L85 PathProgramCache]: Analyzing trace with hash -1018400594, now seen corresponding path program 1 times [2022-04-06 15:41:34,546 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 15:41:34,547 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [524021669] [2022-04-06 15:41:34,547 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 15:41:34,547 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 15:41:34,569 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 15:41:34,569 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [988267722] [2022-04-06 15:41:34,569 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 15:41:34,569 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 15:41:34,569 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 15:41:34,579 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 15:41:34,614 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-04-06 15:41:34,815 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 15:41:34,816 INFO L263 TraceCheckSpWp]: Trace formula consists of 78 conjuncts, 17 conjunts are in the unsatisfiable core [2022-04-06 15:41:34,820 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 15:41:37,823 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 15:41:37,824 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 15:42:11,398 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 15:42:11,398 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 15:42:11,398 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [524021669] [2022-04-06 15:42:11,398 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 15:42:11,398 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [988267722] [2022-04-06 15:42:11,399 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [988267722] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 15:42:11,399 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 15:42:11,399 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 12 [2022-04-06 15:43:49,222 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 15:43:49,223 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [456579806] [2022-04-06 15:43:49,223 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [456579806] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 15:43:49,223 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 15:43:49,223 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [29] imperfect sequences [] total 29 [2022-04-06 15:43:49,223 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [842680108] [2022-04-06 15:43:49,223 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 15:43:49,224 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2022-04-06 15:43:49,224 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 15:43:49,224 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2022-04-06 15:43:49,225 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=191, Invalid=967, Unknown=32, NotChecked=0, Total=1190 [2022-04-06 15:43:49,225 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-04-06 15:44:06,936 WARN L232 SmtUtils]: Spent 5.66s on a formula simplification. DAG size of input: 89 DAG size of output: 78 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 15:44:07,660 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 15:44:07,660 INFO L93 Difference]: Finished difference Result 74 states and 83 transitions. [2022-04-06 15:44:07,661 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2022-04-06 15:44:07,661 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-04-06 15:44:07,662 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 15:44:07,662 INFO L225 Difference]: With dead ends: 74 [2022-04-06 15:44:07,663 INFO L226 Difference]: Without dead ends: 72 [2022-04-06 15:44:07,663 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 86 GetRequests, 41 SyntacticMatches, 8 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 588 ImplicationChecksByTransitivity, 116.0s TimeCoverageRelationStatistics Valid=234, Invalid=1214, Unknown=34, NotChecked=0, Total=1482 [2022-04-06 15:44:07,664 INFO L913 BasicCegarLoop]: 32 mSDtfsCounter, 24 mSDsluCounter, 264 mSDsCounter, 0 mSdLazyCounter, 107 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 296 SdHoareTripleChecker+Invalid, 248 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 107 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 137 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2022-04-06 15:44:07,664 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 296 Invalid, 248 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 107 Invalid, 0 Unknown, 137 Unchecked, 0.7s Time] [2022-04-06 15:44:07,665 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2022-04-06 15:44:07,682 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 72. [2022-04-06 15:44:07,682 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-04-06 15:44:07,683 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 72 states to 72 states and 81 transitions. [2022-04-06 15:44:07,684 INFO L78 Accepts]: Start accepts. Automaton has 72 states and 81 transitions. Word has length 49 [2022-04-06 15:44:07,684 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 15:44:07,684 INFO L478 AbstractCegarLoop]: Abstraction has 72 states and 81 transitions. [2022-04-06 15:44:07,684 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-04-06 15:44:07,684 INFO L276 IsEmpty]: Start isEmpty. Operand 72 states and 81 transitions. [2022-04-06 15:44:07,685 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2022-04-06 15:44:07,685 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 15:44:07,685 INFO L499 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-04-06 15:44:07,691 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-04-06 15:44:07,890 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-04-06 15:44:07,891 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 15:44:07,891 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 15:44:07,891 INFO L85 PathProgramCache]: Analyzing trace with hash -1130038122, now seen corresponding path program 2 times [2022-04-06 15:44:07,891 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 15:44:07,891 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [2043198944] [2022-04-06 15:45:22,581 WARN L232 SmtUtils]: Spent 1.24m 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-04-06 15:45:22,586 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-04-06 15:45:22,588 INFO L271 tedInterpolationCore]: Starting analysis with loop acceleration approximation PRECISE [2022-04-06 15:45:22,590 INFO L85 PathProgramCache]: Analyzing trace with hash 1063970467, now seen corresponding path program 1 times [2022-04-06 15:45:22,590 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 15:45:22,590 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1166249153] [2022-04-06 15:45:22,590 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 15:45:22,590 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 15:45:22,600 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 15:45:22,600 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [281954269] [2022-04-06 15:45:22,600 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 15:45:22,600 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 15:45:22,600 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 15:45:22,607 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 15:45:22,608 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-04-06 15:45:22,826 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-04-06 15:45:22,826 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-04-06 15:45:22,969 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-04-06 15:45:22,988 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-04-06 15:45:22,988 INFO L85 PathProgramCache]: Analyzing trace with hash -1130038122, now seen corresponding path program 3 times [2022-04-06 15:45:22,989 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 15:45:22,989 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1568794107] [2022-04-06 15:45:22,989 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 15:45:22,989 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 15:45:22,996 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 15:45:22,997 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1360101368] [2022-04-06 15:45:22,997 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-04-06 15:45:22,997 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 15:45:22,997 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 15:45:23,007 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 15:45:23,042 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-04-06 15:45:23,077 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2022-04-06 15:45:23,078 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 15:45:23,079 INFO L263 TraceCheckSpWp]: Trace formula consists of 96 conjuncts, 13 conjunts are in the unsatisfiable core [2022-04-06 15:45:23,088 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 15:45:23,797 INFO L134 CoverageAnalysis]: Checked inductivity of 102 backedges. 14 proven. 4 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2022-04-06 15:45:23,797 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 15:45:24,273 INFO L134 CoverageAnalysis]: Checked inductivity of 102 backedges. 14 proven. 4 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2022-04-06 15:45:24,273 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 15:45:24,273 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1568794107] [2022-04-06 15:45:24,274 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 15:45:24,274 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1360101368] [2022-04-06 15:45:24,274 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1360101368] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 15:45:24,274 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 15:45:24,274 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2022-04-06 15:45:24,274 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 15:45:24,274 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [2043198944] [2022-04-06 15:45:24,275 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [2043198944] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 15:45:24,275 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 15:45:24,275 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 15:45:24,275 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [634874932] [2022-04-06 15:45:24,275 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 15:45:24,275 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-06 15:45:24,275 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 15:45:24,276 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-06 15:45:24,276 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2022-04-06 15:45:24,276 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-04-06 15:45:25,093 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 15:45:25,095 INFO L93 Difference]: Finished difference Result 91 states and 110 transitions. [2022-04-06 15:45:25,096 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-06 15:45:25,096 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-04-06 15:45:25,096 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 15:45:25,098 INFO L225 Difference]: With dead ends: 91 [2022-04-06 15:45:25,098 INFO L226 Difference]: Without dead ends: 89 [2022-04-06 15:45:25,098 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 108 GetRequests, 100 SyntacticMatches, 1 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=20, Invalid=52, Unknown=0, NotChecked=0, Total=72 [2022-04-06 15:45:25,099 INFO L913 BasicCegarLoop]: 58 mSDtfsCounter, 6 mSDsluCounter, 138 mSDsCounter, 0 mSdLazyCounter, 107 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 196 SdHoareTripleChecker+Invalid, 109 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 107 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2022-04-06 15:45:25,099 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 196 Invalid, 109 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 107 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2022-04-06 15:45:25,100 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states. [2022-04-06 15:45:25,119 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 80. [2022-04-06 15:45:25,120 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-04-06 15:45:25,124 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 80 states to 80 states and 91 transitions. [2022-04-06 15:45:25,125 INFO L78 Accepts]: Start accepts. Automaton has 80 states and 91 transitions. Word has length 54 [2022-04-06 15:45:25,126 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 15:45:25,126 INFO L478 AbstractCegarLoop]: Abstraction has 80 states and 91 transitions. [2022-04-06 15:45:25,126 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-04-06 15:45:25,127 INFO L276 IsEmpty]: Start isEmpty. Operand 80 states and 91 transitions. [2022-04-06 15:45:25,136 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2022-04-06 15:45:25,136 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 15:45:25,137 INFO L499 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-04-06 15:45:25,149 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-04-06 15:45:25,354 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-04-06 15:45:25,537 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-04-06 15:45:25,538 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 15:45:25,538 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 15:45:25,538 INFO L85 PathProgramCache]: Analyzing trace with hash -1546120389, now seen corresponding path program 4 times [2022-04-06 15:45:25,538 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 15:45:25,538 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1788299196] [2022-04-06 15:47:44,256 WARN L232 SmtUtils]: Spent 2.31m on a formula simplification. DAG size of input: 192 DAG size of output: 188 (called from [L 564] de.uni_freiburg.informatik.ultimate.icfgtransformer.loopacceleration.jordan.JordanLoopAcceleration.buildAccelerationFormula) [2022-04-06 15:47:44,259 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-04-06 15:47:44,260 INFO L271 tedInterpolationCore]: Starting analysis with loop acceleration approximation PRECISE [2022-04-06 15:47:44,262 INFO L85 PathProgramCache]: Analyzing trace with hash 1624834318, now seen corresponding path program 1 times [2022-04-06 15:47:44,262 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 15:47:44,262 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [205406363] [2022-04-06 15:47:44,262 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 15:47:44,262 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 15:47:44,271 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 15:47:44,271 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [943721197] [2022-04-06 15:47:44,272 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 15:47:44,272 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 15:47:44,272 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 15:47:44,276 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 15:47:44,277 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-04-06 15:47:44,668 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 15:47:44,671 INFO L263 TraceCheckSpWp]: Trace formula consists of 96 conjuncts, 27 conjunts are in the unsatisfiable core [2022-04-06 15:47:44,673 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 15:47:54,172 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 3 proven. 3 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-06 15:47:54,172 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 15:47:56,749 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 3 proven. 3 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-06 15:47:56,749 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 15:47:56,749 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [205406363] [2022-04-06 15:47:56,749 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 15:47:56,749 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [943721197] [2022-04-06 15:47:56,750 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [943721197] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 15:47:56,750 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 15:47:56,750 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 13 [2022-04-06 15:49:31,444 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 15:49:31,444 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1788299196] [2022-04-06 15:49:31,445 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1788299196] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 15:49:31,445 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 15:49:31,445 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [29] imperfect sequences [] total 29 [2022-04-06 15:49:31,445 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [314031427] [2022-04-06 15:49:31,445 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 15:49:31,445 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2022-04-06 15:49:31,445 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 15:49:31,446 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2022-04-06 15:49:31,446 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=196, Invalid=1035, Unknown=29, NotChecked=0, Total=1260 [2022-04-06 15:49:31,446 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-04-06 15:49:54,662 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 15:49:54,662 INFO L93 Difference]: Finished difference Result 94 states and 103 transitions. [2022-04-06 15:49:54,662 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2022-04-06 15:49:54,663 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-04-06 15:49:54,663 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 15:49:54,666 INFO L225 Difference]: With dead ends: 94 [2022-04-06 15:49:54,666 INFO L226 Difference]: Without dead ends: 92 [2022-04-06 15:49:54,668 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 108 GetRequests, 59 SyntacticMatches, 8 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 733 ImplicationChecksByTransitivity, 118.2s TimeCoverageRelationStatistics Valid=278, Invalid=1498, Unknown=30, NotChecked=0, Total=1806 [2022-04-06 15:49:54,668 INFO L913 BasicCegarLoop]: 32 mSDtfsCounter, 25 mSDsluCounter, 292 mSDsCounter, 0 mSdLazyCounter, 117 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 324 SdHoareTripleChecker+Invalid, 351 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 117 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 219 IncrementalHoareTripleChecker+Unchecked, 1.2s IncrementalHoareTripleChecker+Time [2022-04-06 15:49:54,669 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [26 Valid, 324 Invalid, 351 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 117 Invalid, 0 Unknown, 219 Unchecked, 1.2s Time] [2022-04-06 15:49:54,669 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2022-04-06 15:49:54,701 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 92. [2022-04-06 15:49:54,702 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-04-06 15:49:54,703 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 92 states to 92 states and 100 transitions. [2022-04-06 15:49:54,703 INFO L78 Accepts]: Start accepts. Automaton has 92 states and 100 transitions. Word has length 59 [2022-04-06 15:49:54,703 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 15:49:54,703 INFO L478 AbstractCegarLoop]: Abstraction has 92 states and 100 transitions. [2022-04-06 15:49:54,703 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-04-06 15:49:54,704 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states and 100 transitions. [2022-04-06 15:49:54,704 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2022-04-06 15:49:54,704 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 15:49:54,704 INFO L499 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-04-06 15:49:54,716 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2022-04-06 15:49:54,912 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-04-06 15:49:54,913 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 15:49:54,913 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 15:49:54,913 INFO L85 PathProgramCache]: Analyzing trace with hash -389057674, now seen corresponding path program 5 times [2022-04-06 15:49:54,913 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 15:49:54,913 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [332499371] [2022-04-06 15:51:31,407 WARN L232 SmtUtils]: Spent 1.61m on a formula simplification. DAG size of input: 195 DAG size of output: 193 (called from [L 564] de.uni_freiburg.informatik.ultimate.icfgtransformer.loopacceleration.jordan.JordanLoopAcceleration.buildAccelerationFormula) [2022-04-06 15:51:31,410 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-04-06 15:51:31,411 INFO L271 tedInterpolationCore]: Starting analysis with loop acceleration approximation PRECISE [2022-04-06 15:51:31,411 INFO L85 PathProgramCache]: Analyzing trace with hash 746353091, now seen corresponding path program 1 times [2022-04-06 15:51:31,412 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 15:51:31,412 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [257532223] [2022-04-06 15:51:31,412 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 15:51:31,412 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 15:51:31,431 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 15:51:31,432 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1674871525] [2022-04-06 15:51:31,432 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 15:51:31,432 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 15:51:31,432 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 15:51:31,447 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 15:51:31,474 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-04-06 15:51:32,325 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 15:51:32,328 INFO L263 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 39 conjunts are in the unsatisfiable core [2022-04-06 15:51:32,330 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 15:52:17,650 WARN L232 SmtUtils]: Spent 16.37s on a formula simplification. DAG size of input: 111 DAG size of output: 110 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 15:53:24,459 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 4 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-04-06 15:53:24,460 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 15:53:40,859 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 14 proven. 3 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-04-06 15:53:40,859 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 15:53:40,859 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [257532223] [2022-04-06 15:53:40,859 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 15:53:40,860 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1674871525] [2022-04-06 15:53:40,860 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1674871525] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 15:53:40,860 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 15:53:40,860 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 9] total 18