/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/egcd3-ll_unwindbound5.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-34549b5 [2022-04-06 16:41:10,961 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-06 16:41:10,963 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-06 16:41:10,979 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-06 16:41:10,980 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-06 16:41:10,980 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-06 16:41:10,981 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-06 16:41:10,982 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-06 16:41:10,983 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-06 16:41:10,984 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-06 16:41:10,984 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-06 16:41:10,985 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-06 16:41:10,985 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-06 16:41:10,986 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-06 16:41:10,987 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-06 16:41:10,987 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-06 16:41:10,988 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-06 16:41:10,988 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-06 16:41:10,990 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-06 16:41:10,991 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-06 16:41:10,992 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-06 16:41:10,992 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-06 16:41:10,993 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-06 16:41:10,994 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-06 16:41:10,994 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-06 16:41:10,996 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-06 16:41:10,996 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-06 16:41:10,997 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-06 16:41:10,997 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-06 16:41:10,997 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-06 16:41:10,998 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-06 16:41:10,998 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-06 16:41:10,999 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-06 16:41:10,999 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-06 16:41:11,000 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-06 16:41:11,000 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-06 16:41:11,000 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-06 16:41:11,001 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-06 16:41:11,001 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-06 16:41:11,001 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-06 16:41:11,002 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-06 16:41:11,008 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-06 16:41:11,008 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 16:41:11,014 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-06 16:41:11,014 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-06 16:41:11,014 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-06 16:41:11,014 INFO L138 SettingsManager]: * sizeof long=4 [2022-04-06 16:41:11,015 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-06 16:41:11,015 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-04-06 16:41:11,015 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-06 16:41:11,015 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-06 16:41:11,015 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-06 16:41:11,015 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-06 16:41:11,015 INFO L138 SettingsManager]: * sizeof long double=12 [2022-04-06 16:41:11,015 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-06 16:41:11,016 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-06 16:41:11,016 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-06 16:41:11,016 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-06 16:41:11,016 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-06 16:41:11,016 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-06 16:41:11,016 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-06 16:41:11,016 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-06 16:41:11,016 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-06 16:41:11,017 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-04-06 16:41:11,017 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-04-06 16:41:11,017 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-04-06 16:41:11,017 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-06 16:41:11,017 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=JORDAN [2022-04-06 16:41:11,017 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 16:41:11,210 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-06 16:41:11,225 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-06 16:41:11,227 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-06 16:41:11,228 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-06 16:41:11,228 INFO L275 PluginConnector]: CDTParser initialized [2022-04-06 16:41:11,229 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/egcd3-ll_unwindbound5.c [2022-04-06 16:41:11,279 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/9d50fe146/4482ccb1e74247949cd570d52987966d/FLAGe621a087d [2022-04-06 16:41:11,624 INFO L306 CDTParser]: Found 1 translation units. [2022-04-06 16:41:11,624 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/egcd3-ll_unwindbound5.c [2022-04-06 16:41:11,630 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/9d50fe146/4482ccb1e74247949cd570d52987966d/FLAGe621a087d [2022-04-06 16:41:11,643 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/9d50fe146/4482ccb1e74247949cd570d52987966d [2022-04-06 16:41:11,645 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-06 16:41:11,646 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-06 16:41:11,647 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-06 16:41:11,647 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-06 16:41:11,650 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-06 16:41:11,650 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 04:41:11" (1/1) ... [2022-04-06 16:41:11,651 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@46d21ecb and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 04:41:11, skipping insertion in model container [2022-04-06 16:41:11,651 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 04:41:11" (1/1) ... [2022-04-06 16:41:11,655 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-06 16:41:11,666 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-06 16:41:11,790 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/egcd3-ll_unwindbound5.c[490,503] [2022-04-06 16:41:11,805 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-06 16:41:11,810 INFO L203 MainTranslator]: Completed pre-run [2022-04-06 16:41:11,817 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/egcd3-ll_unwindbound5.c[490,503] [2022-04-06 16:41:11,835 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-06 16:41:11,844 INFO L208 MainTranslator]: Completed translation [2022-04-06 16:41:11,844 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 04:41:11 WrapperNode [2022-04-06 16:41:11,844 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-06 16:41:11,845 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-06 16:41:11,845 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-06 16:41:11,846 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-06 16:41:11,852 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 04:41:11" (1/1) ... [2022-04-06 16:41:11,852 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 04:41:11" (1/1) ... [2022-04-06 16:41:11,862 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 04:41:11" (1/1) ... [2022-04-06 16:41:11,863 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 04:41:11" (1/1) ... [2022-04-06 16:41:11,872 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 04:41:11" (1/1) ... [2022-04-06 16:41:11,874 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 04:41:11" (1/1) ... [2022-04-06 16:41:11,875 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 04:41:11" (1/1) ... [2022-04-06 16:41:11,876 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-06 16:41:11,876 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-06 16:41:11,877 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-06 16:41:11,877 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-06 16:41:11,882 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 04:41:11" (1/1) ... [2022-04-06 16:41:11,886 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-06 16:41:11,892 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 16:41:11,912 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 16:41:11,922 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 16:41:11,937 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-06 16:41:11,937 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-06 16:41:11,937 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-06 16:41:11,938 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-06 16:41:11,938 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-06 16:41:11,938 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-06 16:41:11,938 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-06 16:41:11,938 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-06 16:41:11,939 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-06 16:41:11,939 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-06 16:41:11,939 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-04-06 16:41:11,940 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-06 16:41:11,940 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-06 16:41:11,940 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-06 16:41:11,940 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-06 16:41:11,940 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-06 16:41:11,941 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-06 16:41:11,941 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-06 16:41:11,941 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-06 16:41:11,941 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-06 16:41:11,981 INFO L234 CfgBuilder]: Building ICFG [2022-04-06 16:41:11,982 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-06 16:41:12,113 INFO L275 CfgBuilder]: Performing block encoding [2022-04-06 16:41:12,116 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-06 16:41:12,117 INFO L299 CfgBuilder]: Removed 3 assume(true) statements. [2022-04-06 16:41:12,118 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 04:41:12 BoogieIcfgContainer [2022-04-06 16:41:12,118 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-06 16:41:12,119 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-06 16:41:12,119 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-06 16:41:12,122 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-06 16:41:12,122 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 06.04 04:41:11" (1/3) ... [2022-04-06 16:41:12,122 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2df4d339 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 04:41:12, skipping insertion in model container [2022-04-06 16:41:12,122 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 04:41:11" (2/3) ... [2022-04-06 16:41:12,123 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2df4d339 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 04:41:12, skipping insertion in model container [2022-04-06 16:41:12,123 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 04:41:12" (3/3) ... [2022-04-06 16:41:12,124 INFO L111 eAbstractionObserver]: Analyzing ICFG egcd3-ll_unwindbound5.c [2022-04-06 16:41:12,127 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-04-06 16:41:12,127 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-06 16:41:12,173 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-06 16:41:12,177 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 16:41:12,178 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-06 16:41:12,200 INFO L276 IsEmpty]: Start isEmpty. Operand has 40 states, 25 states have (on average 1.48) internal successors, (37), 26 states have internal predecessors, (37), 9 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-06 16:41:12,206 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2022-04-06 16:41:12,206 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 16:41:12,206 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 16:41:12,207 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 16:41:12,211 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 16:41:12,211 INFO L85 PathProgramCache]: Analyzing trace with hash 1766263304, now seen corresponding path program 1 times [2022-04-06 16:41:12,231 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:12,231 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1335125671] [2022-04-06 16:41:12,239 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 16:41:12,239 INFO L85 PathProgramCache]: Analyzing trace with hash 1766263304, now seen corresponding path program 2 times [2022-04-06 16:41:12,241 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 16:41:12,241 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1666402455] [2022-04-06 16:41:12,241 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 16:41:12,242 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 16:41:12,347 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 16:41:12,408 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-06 16:41:12,413 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 16:41:12,422 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-06 16:41:12,425 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 16:41:12,431 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2022-04-06 16:41:12,432 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 16:41:12,454 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-06 16:41:12,455 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 16:41:12,455 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1666402455] [2022-04-06 16:41:12,455 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1666402455] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 16:41:12,455 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 16:41:12,456 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-06 16:41:12,457 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 16:41:12,457 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1335125671] [2022-04-06 16:41:12,458 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1335125671] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 16:41:12,458 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 16:41:12,458 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-06 16:41:12,458 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [378530598] [2022-04-06 16:41:12,458 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 16:41:12,461 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-06 16:41:12,461 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:12,483 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-06 16:41:12,484 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-06 16:41:12,486 INFO L87 Difference]: Start difference. First operand has 40 states, 25 states have (on average 1.48) internal successors, (37), 26 states have internal predecessors, (37), 9 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) 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, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-06 16:41:12,578 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 16:41:12,578 INFO L93 Difference]: Finished difference Result 74 states and 111 transitions. [2022-04-06 16:41:12,579 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-06 16:41:12,580 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, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 22 [2022-04-06 16:41:12,580 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 16:41:12,585 INFO L225 Difference]: With dead ends: 74 [2022-04-06 16:41:12,585 INFO L226 Difference]: Without dead ends: 36 [2022-04-06 16:41:12,588 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 9 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 16:41:12,593 INFO L913 BasicCegarLoop]: 47 mSDtfsCounter, 10 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 51 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 16:41:12,594 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 51 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 16:41:12,609 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2022-04-06 16:41:12,634 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 35. [2022-04-06 16:41:12,635 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 22 states have (on average 1.3181818181818181) internal successors, (29), 23 states have internal predecessors, (29), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-06 16:41:12,638 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 45 transitions. [2022-04-06 16:41:12,639 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 45 transitions. Word has length 22 [2022-04-06 16:41:12,639 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 16:41:12,639 INFO L478 AbstractCegarLoop]: Abstraction has 35 states and 45 transitions. [2022-04-06 16:41:12,640 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, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-06 16:41:12,640 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 45 transitions. [2022-04-06 16:41:12,642 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2022-04-06 16:41:12,642 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 16:41:12,643 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 16:41:12,643 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-06 16:41:12,643 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 16:41:12,645 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 16:41:12,645 INFO L85 PathProgramCache]: Analyzing trace with hash -81203399, now seen corresponding path program 1 times [2022-04-06 16:41:12,645 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:12,645 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [650465223] [2022-04-06 16:41:12,653 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 16:41:12,653 INFO L85 PathProgramCache]: Analyzing trace with hash -81203399, now seen corresponding path program 2 times [2022-04-06 16:41:12,653 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 16:41:12,653 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1811795185] [2022-04-06 16:41:12,654 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 16:41:12,654 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 16:41:12,675 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 16:41:12,678 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2018865750] [2022-04-06 16:41:12,678 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 16:41:12,678 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 16:41:12,678 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 16:41:12,679 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 16:41:12,680 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 16:41:12,728 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-04-06 16:41:12,728 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 16:41:12,729 INFO L263 TraceCheckSpWp]: Trace formula consists of 90 conjuncts, 5 conjunts are in the unsatisfiable core [2022-04-06 16:41:12,733 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 16:41:12,816 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-06 16:41:12,816 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 16:41:12,816 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 16:41:12,816 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1811795185] [2022-04-06 16:41:12,817 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 16:41:12,817 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2018865750] [2022-04-06 16:41:12,817 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2018865750] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 16:41:12,817 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 16:41:12,817 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-06 16:41:12,818 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 16:41:12,818 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [650465223] [2022-04-06 16:41:12,818 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [650465223] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 16:41:12,818 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 16:41:12,818 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-06 16:41:12,818 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [688898129] [2022-04-06 16:41:12,818 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 16:41:12,819 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-04-06 16:41:12,819 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:12,819 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-04-06 16:41:12,819 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-04-06 16:41:12,820 INFO L87 Difference]: Start difference. First operand 35 states and 45 transitions. Second operand has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-06 16:41:12,831 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 16:41:12,831 INFO L93 Difference]: Finished difference Result 44 states and 54 transitions. [2022-04-06 16:41:12,831 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-04-06 16:41:12,832 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) Word has length 23 [2022-04-06 16:41:12,832 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 16:41:12,832 INFO L225 Difference]: With dead ends: 44 [2022-04-06 16:41:12,833 INFO L226 Difference]: Without dead ends: 37 [2022-04-06 16:41:12,833 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-04-06 16:41:12,834 INFO L913 BasicCegarLoop]: 43 mSDtfsCounter, 0 mSDsluCounter, 70 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 113 SdHoareTripleChecker+Invalid, 9 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 16:41:12,834 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 113 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 16:41:12,834 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2022-04-06 16:41:12,839 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 37. [2022-04-06 16:41:12,839 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 24 states have (on average 1.2916666666666667) internal successors, (31), 25 states have internal predecessors, (31), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-06 16:41:12,840 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 47 transitions. [2022-04-06 16:41:12,840 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 47 transitions. Word has length 23 [2022-04-06 16:41:12,841 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 16:41:12,841 INFO L478 AbstractCegarLoop]: Abstraction has 37 states and 47 transitions. [2022-04-06 16:41:12,841 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-06 16:41:12,841 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 47 transitions. [2022-04-06 16:41:12,841 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2022-04-06 16:41:12,841 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 16:41:12,842 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 16:41:12,861 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-04-06 16:41:13,060 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 16:41:13,061 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 16:41:13,061 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 16:41:13,061 INFO L85 PathProgramCache]: Analyzing trace with hash 1762644405, now seen corresponding path program 1 times [2022-04-06 16:41:13,061 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:13,062 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [720484679] [2022-04-06 16:41:13,062 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 16:41:13,062 INFO L85 PathProgramCache]: Analyzing trace with hash 1762644405, now seen corresponding path program 2 times [2022-04-06 16:41:13,062 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 16:41:13,062 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [334106591] [2022-04-06 16:41:13,062 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 16:41:13,063 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 16:41:13,074 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 16:41:13,074 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [20408349] [2022-04-06 16:41:13,074 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 16:41:13,075 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 16:41:13,075 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 16:41:13,092 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 16:41:13,093 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 16:41:13,131 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-04-06 16:41:13,132 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 16:41:13,133 INFO L263 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 19 conjunts are in the unsatisfiable core [2022-04-06 16:41:13,139 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 16:41:13,306 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-06 16:41:13,306 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 16:41:13,306 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 16:41:13,307 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [334106591] [2022-04-06 16:41:13,307 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 16:41:13,307 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [20408349] [2022-04-06 16:41:13,307 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [20408349] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 16:41:13,307 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 16:41:13,307 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 16:41:13,308 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 16:41:13,308 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [720484679] [2022-04-06 16:41:13,308 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [720484679] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 16:41:13,308 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 16:41:13,308 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 16:41:13,308 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [524962284] [2022-04-06 16:41:13,308 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 16:41:13,309 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-06 16:41:13,309 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:13,310 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-06 16:41:13,310 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-04-06 16:41:13,310 INFO L87 Difference]: Start difference. First operand 37 states and 47 transitions. Second operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-06 16:41:13,392 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 16:41:13,392 INFO L93 Difference]: Finished difference Result 57 states and 75 transitions. [2022-04-06 16:41:13,392 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-06 16:41:13,392 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 24 [2022-04-06 16:41:13,393 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 16:41:13,393 INFO L225 Difference]: With dead ends: 57 [2022-04-06 16:41:13,393 INFO L226 Difference]: Without dead ends: 54 [2022-04-06 16:41:13,394 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 25 GetRequests, 19 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2022-04-06 16:41:13,394 INFO L913 BasicCegarLoop]: 41 mSDtfsCounter, 18 mSDsluCounter, 131 mSDsCounter, 0 mSdLazyCounter, 73 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 172 SdHoareTripleChecker+Invalid, 75 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 73 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 16:41:13,395 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [22 Valid, 172 Invalid, 75 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 73 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 16:41:13,395 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2022-04-06 16:41:13,419 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 53. [2022-04-06 16:41:13,420 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 53 states, 35 states have (on average 1.3142857142857143) internal successors, (46), 36 states have internal predecessors, (46), 13 states have call successors, (13), 5 states have call predecessors, (13), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-06 16:41:13,424 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 70 transitions. [2022-04-06 16:41:13,424 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 70 transitions. Word has length 24 [2022-04-06 16:41:13,425 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 16:41:13,425 INFO L478 AbstractCegarLoop]: Abstraction has 53 states and 70 transitions. [2022-04-06 16:41:13,425 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-06 16:41:13,425 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 70 transitions. [2022-04-06 16:41:13,426 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2022-04-06 16:41:13,426 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 16:41:13,426 INFO L499 BasicCegarLoop]: trace histogram [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] [2022-04-06 16:41:13,449 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 16:41:13,626 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2022-04-06 16:41:13,626 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 16:41:13,627 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 16:41:13,627 INFO L85 PathProgramCache]: Analyzing trace with hash -1090347867, now seen corresponding path program 1 times [2022-04-06 16:41:13,627 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:13,627 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [856661263] [2022-04-06 16:41:13,628 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 16:41:13,628 INFO L85 PathProgramCache]: Analyzing trace with hash -1090347867, now seen corresponding path program 2 times [2022-04-06 16:41:13,628 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 16:41:13,628 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1790812521] [2022-04-06 16:41:13,628 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 16:41:13,628 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 16:41:13,646 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 16:41:13,647 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1978692806] [2022-04-06 16:41:13,647 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 16:41:13,647 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 16:41:13,647 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 16:41:13,663 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 16:41:13,664 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 16:41:13,700 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 16:41:13,700 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 16:41:13,701 INFO L263 TraceCheckSpWp]: Trace formula consists of 128 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-06 16:41:13,704 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 16:41:13,770 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-06 16:41:13,770 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 16:41:13,770 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 16:41:13,770 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1790812521] [2022-04-06 16:41:13,770 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 16:41:13,771 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1978692806] [2022-04-06 16:41:13,771 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1978692806] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 16:41:13,771 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 16:41:13,771 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 16:41:13,771 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 16:41:13,771 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [856661263] [2022-04-06 16:41:13,772 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [856661263] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 16:41:13,772 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 16:41:13,772 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 16:41:13,772 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2140760830] [2022-04-06 16:41:13,772 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 16:41:13,772 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 16:41:13,772 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:13,773 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 16:41:13,773 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-04-06 16:41:13,773 INFO L87 Difference]: Start difference. First operand 53 states and 70 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-06 16:41:13,792 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 16:41:13,792 INFO L93 Difference]: Finished difference Result 77 states and 104 transitions. [2022-04-06 16:41:13,792 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 16:41:13,792 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) Word has length 29 [2022-04-06 16:41:13,792 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 16:41:13,793 INFO L225 Difference]: With dead ends: 77 [2022-04-06 16:41:13,794 INFO L226 Difference]: Without dead ends: 55 [2022-04-06 16:41:13,794 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 28 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-04-06 16:41:13,795 INFO L913 BasicCegarLoop]: 42 mSDtfsCounter, 6 mSDsluCounter, 71 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 113 SdHoareTripleChecker+Invalid, 19 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 16:41:13,795 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 113 Invalid, 19 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 16:41:13,795 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2022-04-06 16:41:13,800 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2022-04-06 16:41:13,800 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 37 states have (on average 1.2972972972972974) internal successors, (48), 38 states have internal predecessors, (48), 13 states have call successors, (13), 5 states have call predecessors, (13), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-06 16:41:13,801 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 72 transitions. [2022-04-06 16:41:13,801 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 72 transitions. Word has length 29 [2022-04-06 16:41:13,801 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 16:41:13,801 INFO L478 AbstractCegarLoop]: Abstraction has 55 states and 72 transitions. [2022-04-06 16:41:13,802 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-06 16:41:13,802 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 72 transitions. [2022-04-06 16:41:13,802 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2022-04-06 16:41:13,802 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 16:41:13,802 INFO L499 BasicCegarLoop]: trace histogram [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 16:41:13,818 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 16:41:14,018 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 16:41:14,019 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 16:41:14,019 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 16:41:14,019 INFO L85 PathProgramCache]: Analyzing trace with hash 979890972, now seen corresponding path program 1 times [2022-04-06 16:41:14,019 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:14,019 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [189959147] [2022-04-06 16:41:14,020 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 16:41:14,020 INFO L85 PathProgramCache]: Analyzing trace with hash 979890972, now seen corresponding path program 2 times [2022-04-06 16:41:14,020 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 16:41:14,020 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2141066129] [2022-04-06 16:41:14,020 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 16:41:14,020 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 16:41:14,033 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 16:41:14,034 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1254544222] [2022-04-06 16:41:14,034 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 16:41:14,034 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 16:41:14,034 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 16:41:14,035 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 16:41:14,036 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 16:41:14,070 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 16:41:14,070 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 16:41:14,071 INFO L263 TraceCheckSpWp]: Trace formula consists of 129 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-06 16:41:14,072 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 16:41:14,128 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-06 16:41:14,128 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 16:41:14,194 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-06 16:41:14,194 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 16:41:14,194 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2141066129] [2022-04-06 16:41:14,195 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 16:41:14,195 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1254544222] [2022-04-06 16:41:14,195 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1254544222] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 16:41:14,195 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 16:41:14,195 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2022-04-06 16:41:14,195 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 16:41:14,195 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [189959147] [2022-04-06 16:41:14,195 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [189959147] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 16:41:14,195 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 16:41:14,195 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 16:41:14,196 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1106867358] [2022-04-06 16:41:14,196 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 16:41:14,196 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-06 16:41:14,196 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:14,196 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-06 16:41:14,196 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=46, Unknown=0, NotChecked=0, Total=72 [2022-04-06 16:41:14,197 INFO L87 Difference]: Start difference. First operand 55 states and 72 transitions. Second operand has 6 states, 6 states have (on average 3.1666666666666665) internal successors, (19), 5 states have internal predecessors, (19), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-06 16:41:14,221 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 16:41:14,222 INFO L93 Difference]: Finished difference Result 67 states and 85 transitions. [2022-04-06 16:41:14,222 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-06 16:41:14,222 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 3.1666666666666665) internal successors, (19), 5 states have internal predecessors, (19), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) Word has length 30 [2022-04-06 16:41:14,222 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 16:41:14,223 INFO L225 Difference]: With dead ends: 67 [2022-04-06 16:41:14,223 INFO L226 Difference]: Without dead ends: 60 [2022-04-06 16:41:14,223 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 60 GetRequests, 51 SyntacticMatches, 1 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=34, Invalid=56, Unknown=0, NotChecked=0, Total=90 [2022-04-06 16:41:14,223 INFO L913 BasicCegarLoop]: 41 mSDtfsCounter, 14 mSDsluCounter, 100 mSDsCounter, 0 mSdLazyCounter, 18 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 141 SdHoareTripleChecker+Invalid, 34 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 18 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 16:41:14,224 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 141 Invalid, 34 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 18 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 16:41:14,224 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2022-04-06 16:41:14,228 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 59. [2022-04-06 16:41:14,229 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 41 states have (on average 1.2926829268292683) internal successors, (53), 42 states have internal predecessors, (53), 13 states have call successors, (13), 5 states have call predecessors, (13), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-06 16:41:14,229 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 77 transitions. [2022-04-06 16:41:14,230 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 77 transitions. Word has length 30 [2022-04-06 16:41:14,230 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 16:41:14,230 INFO L478 AbstractCegarLoop]: Abstraction has 59 states and 77 transitions. [2022-04-06 16:41:14,230 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 3.1666666666666665) internal successors, (19), 5 states have internal predecessors, (19), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-06 16:41:14,230 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 77 transitions. [2022-04-06 16:41:14,231 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2022-04-06 16:41:14,231 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 16:41:14,231 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 16:41:14,248 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2022-04-06 16:41:14,437 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 16:41:14,437 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 16:41:14,438 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 16:41:14,438 INFO L85 PathProgramCache]: Analyzing trace with hash 296831538, now seen corresponding path program 1 times [2022-04-06 16:41:14,438 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:14,438 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1731996229] [2022-04-06 16:41:14,439 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 16:41:14,439 INFO L85 PathProgramCache]: Analyzing trace with hash 296831538, now seen corresponding path program 2 times [2022-04-06 16:41:14,440 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 16:41:14,440 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [516527231] [2022-04-06 16:41:14,440 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 16:41:14,441 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 16:41:14,452 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 16:41:14,453 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [740026220] [2022-04-06 16:41:14,453 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 16:41:14,453 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 16:41:14,453 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 16:41:14,457 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 16:41:14,472 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 16:41:14,509 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 16:41:14,509 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 16:41:14,509 INFO L263 TraceCheckSpWp]: Trace formula consists of 131 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-06 16:41:14,511 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 16:41:14,578 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-04-06 16:41:14,578 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 16:41:14,660 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-04-06 16:41:14,660 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 16:41:14,660 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [516527231] [2022-04-06 16:41:14,660 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 16:41:14,660 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [740026220] [2022-04-06 16:41:14,660 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [740026220] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 16:41:14,660 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 16:41:14,661 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 9 [2022-04-06 16:41:14,661 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 16:41:14,661 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1731996229] [2022-04-06 16:41:14,661 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1731996229] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 16:41:14,661 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 16:41:14,661 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-04-06 16:41:14,661 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1819162676] [2022-04-06 16:41:14,661 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 16:41:14,661 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-04-06 16:41:14,661 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:14,662 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-04-06 16:41:14,662 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2022-04-06 16:41:14,662 INFO L87 Difference]: Start difference. First operand 59 states and 77 transitions. Second operand has 8 states, 8 states have (on average 2.875) internal successors, (23), 7 states have internal predecessors, (23), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-06 16:41:14,857 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 16:41:14,857 INFO L93 Difference]: Finished difference Result 138 states and 201 transitions. [2022-04-06 16:41:14,857 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-04-06 16:41:14,858 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.875) internal successors, (23), 7 states have internal predecessors, (23), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 31 [2022-04-06 16:41:14,858 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 16:41:14,859 INFO L225 Difference]: With dead ends: 138 [2022-04-06 16:41:14,859 INFO L226 Difference]: Without dead ends: 131 [2022-04-06 16:41:14,859 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 68 GetRequests, 53 SyntacticMatches, 1 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=60, Invalid=180, Unknown=0, NotChecked=0, Total=240 [2022-04-06 16:41:14,859 INFO L913 BasicCegarLoop]: 65 mSDtfsCounter, 115 mSDsluCounter, 239 mSDsCounter, 0 mSdLazyCounter, 155 mSolverCounterSat, 63 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 119 SdHoareTripleChecker+Valid, 304 SdHoareTripleChecker+Invalid, 218 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 63 IncrementalHoareTripleChecker+Valid, 155 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 16:41:14,860 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [119 Valid, 304 Invalid, 218 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [63 Valid, 155 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 16:41:14,860 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 131 states. [2022-04-06 16:41:14,870 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 131 to 88. [2022-04-06 16:41:14,870 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 88 states, 66 states have (on average 1.3636363636363635) internal successors, (90), 67 states have internal predecessors, (90), 17 states have call successors, (17), 5 states have call predecessors, (17), 4 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2022-04-06 16:41:14,871 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 122 transitions. [2022-04-06 16:41:14,871 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 122 transitions. Word has length 31 [2022-04-06 16:41:14,871 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 16:41:14,871 INFO L478 AbstractCegarLoop]: Abstraction has 88 states and 122 transitions. [2022-04-06 16:41:14,871 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.875) internal successors, (23), 7 states have internal predecessors, (23), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-06 16:41:14,871 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 122 transitions. [2022-04-06 16:41:14,872 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2022-04-06 16:41:14,872 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 16:41:14,872 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 16:41:14,888 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2022-04-06 16:41:15,072 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 16:41:15,073 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 16:41:15,073 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 16:41:15,073 INFO L85 PathProgramCache]: Analyzing trace with hash 1911367052, now seen corresponding path program 1 times [2022-04-06 16:41:15,073 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:15,073 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [483938313] [2022-04-06 16:41:15,074 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 16:41:15,074 INFO L85 PathProgramCache]: Analyzing trace with hash 1911367052, now seen corresponding path program 2 times [2022-04-06 16:41:15,074 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 16:41:15,074 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1813177426] [2022-04-06 16:41:15,074 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 16:41:15,074 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 16:41:15,086 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 16:41:15,086 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1371830092] [2022-04-06 16:41:15,086 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 16:41:15,086 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 16:41:15,086 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 16:41:15,087 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 16:41:15,088 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 16:41:15,121 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 16:41:15,121 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 16:41:15,122 INFO L263 TraceCheckSpWp]: Trace formula consists of 147 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-06 16:41:15,123 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 16:41:15,183 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 16:41:15,183 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 16:41:15,183 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 16:41:15,183 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1813177426] [2022-04-06 16:41:15,183 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 16:41:15,183 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1371830092] [2022-04-06 16:41:15,184 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1371830092] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 16:41:15,184 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 16:41:15,184 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 16:41:15,184 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 16:41:15,184 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [483938313] [2022-04-06 16:41:15,184 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [483938313] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 16:41:15,184 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 16:41:15,184 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 16:41:15,184 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [566989317] [2022-04-06 16:41:15,184 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 16:41:15,184 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-06 16:41:15,185 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:15,185 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-06 16:41:15,185 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2022-04-06 16:41:15,185 INFO L87 Difference]: Start difference. First operand 88 states and 122 transitions. Second operand has 6 states, 6 states have (on average 4.0) internal successors, (24), 5 states have internal predecessors, (24), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-06 16:41:15,228 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 16:41:15,228 INFO L93 Difference]: Finished difference Result 127 states and 178 transitions. [2022-04-06 16:41:15,228 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-06 16:41:15,229 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 4.0) internal successors, (24), 5 states have internal predecessors, (24), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) Word has length 35 [2022-04-06 16:41:15,229 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 16:41:15,229 INFO L225 Difference]: With dead ends: 127 [2022-04-06 16:41:15,229 INFO L226 Difference]: Without dead ends: 90 [2022-04-06 16:41:15,230 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2022-04-06 16:41:15,230 INFO L913 BasicCegarLoop]: 41 mSDtfsCounter, 16 mSDsluCounter, 74 mSDsCounter, 0 mSdLazyCounter, 15 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 115 SdHoareTripleChecker+Invalid, 30 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 15 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 16:41:15,230 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [16 Valid, 115 Invalid, 30 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 15 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 16:41:15,231 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states. [2022-04-06 16:41:15,239 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 90. [2022-04-06 16:41:15,239 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 90 states, 68 states have (on average 1.3529411764705883) internal successors, (92), 69 states have internal predecessors, (92), 17 states have call successors, (17), 5 states have call predecessors, (17), 4 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2022-04-06 16:41:15,240 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 90 states to 90 states and 124 transitions. [2022-04-06 16:41:15,240 INFO L78 Accepts]: Start accepts. Automaton has 90 states and 124 transitions. Word has length 35 [2022-04-06 16:41:15,240 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 16:41:15,240 INFO L478 AbstractCegarLoop]: Abstraction has 90 states and 124 transitions. [2022-04-06 16:41:15,240 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 4.0) internal successors, (24), 5 states have internal predecessors, (24), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-06 16:41:15,241 INFO L276 IsEmpty]: Start isEmpty. Operand 90 states and 124 transitions. [2022-04-06 16:41:15,241 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2022-04-06 16:41:15,241 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 16:41:15,241 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 16:41:15,279 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 16:41:15,457 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 16:41:15,458 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 16:41:15,458 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 16:41:15,458 INFO L85 PathProgramCache]: Analyzing trace with hash -304485816, now seen corresponding path program 1 times [2022-04-06 16:41:15,458 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:15,458 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1685641896] [2022-04-06 16:41:15,459 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 16:41:15,459 INFO L85 PathProgramCache]: Analyzing trace with hash -304485816, now seen corresponding path program 2 times [2022-04-06 16:41:15,459 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 16:41:15,459 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2080109750] [2022-04-06 16:41:15,459 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 16:41:15,459 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 16:41:15,467 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 16:41:15,468 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [526531325] [2022-04-06 16:41:15,468 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 16:41:15,468 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 16:41:15,468 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 16:41:15,476 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 16:41:15,477 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-04-06 16:41:15,522 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 16:41:15,523 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 16:41:15,523 INFO L263 TraceCheckSpWp]: Trace formula consists of 158 conjuncts, 11 conjunts are in the unsatisfiable core [2022-04-06 16:41:15,525 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 16:41:15,591 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 5 proven. 5 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-06 16:41:15,591 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 16:41:15,655 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 5 proven. 5 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-06 16:41:15,655 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 16:41:15,655 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2080109750] [2022-04-06 16:41:15,655 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 16:41:15,655 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [526531325] [2022-04-06 16:41:15,656 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [526531325] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 16:41:15,656 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 16:41:15,656 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 9 [2022-04-06 16:41:15,656 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 16:41:15,656 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1685641896] [2022-04-06 16:41:15,656 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1685641896] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 16:41:15,656 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 16:41:15,656 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-04-06 16:41:15,656 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [638914104] [2022-04-06 16:41:15,656 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 16:41:15,656 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-04-06 16:41:15,656 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:15,657 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-04-06 16:41:15,657 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=46, Unknown=0, NotChecked=0, Total=72 [2022-04-06 16:41:15,657 INFO L87 Difference]: Start difference. First operand 90 states and 124 transitions. Second operand has 7 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 6 states have internal predecessors, (25), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-06 16:41:15,701 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 16:41:15,701 INFO L93 Difference]: Finished difference Result 163 states and 227 transitions. [2022-04-06 16:41:15,701 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-06 16:41:15,701 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 6 states have internal predecessors, (25), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) Word has length 36 [2022-04-06 16:41:15,701 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 16:41:15,702 INFO L225 Difference]: With dead ends: 163 [2022-04-06 16:41:15,702 INFO L226 Difference]: Without dead ends: 112 [2022-04-06 16:41:15,703 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 72 GetRequests, 63 SyntacticMatches, 1 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2022-04-06 16:41:15,703 INFO L913 BasicCegarLoop]: 48 mSDtfsCounter, 41 mSDsluCounter, 116 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 25 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 164 SdHoareTripleChecker+Invalid, 63 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 25 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 16:41:15,703 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [41 Valid, 164 Invalid, 63 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [25 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 16:41:15,704 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 112 states. [2022-04-06 16:41:15,713 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 112 to 109. [2022-04-06 16:41:15,713 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 109 states, 81 states have (on average 1.3209876543209877) internal successors, (107), 82 states have internal predecessors, (107), 21 states have call successors, (21), 7 states have call predecessors, (21), 6 states have return successors, (19), 19 states have call predecessors, (19), 19 states have call successors, (19) [2022-04-06 16:41:15,714 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 109 states to 109 states and 147 transitions. [2022-04-06 16:41:15,714 INFO L78 Accepts]: Start accepts. Automaton has 109 states and 147 transitions. Word has length 36 [2022-04-06 16:41:15,714 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 16:41:15,714 INFO L478 AbstractCegarLoop]: Abstraction has 109 states and 147 transitions. [2022-04-06 16:41:15,714 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 6 states have internal predecessors, (25), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-06 16:41:15,714 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states and 147 transitions. [2022-04-06 16:41:15,715 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2022-04-06 16:41:15,715 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 16:41:15,715 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 16:41:15,733 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2022-04-06 16:41:15,927 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 16:41:15,928 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 16:41:15,928 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 16:41:15,928 INFO L85 PathProgramCache]: Analyzing trace with hash 1581560821, now seen corresponding path program 1 times [2022-04-06 16:41:15,928 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:15,928 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1028963858] [2022-04-06 16:41:15,929 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 16:41:15,929 INFO L85 PathProgramCache]: Analyzing trace with hash 1581560821, now seen corresponding path program 2 times [2022-04-06 16:41:15,929 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 16:41:15,929 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [513068431] [2022-04-06 16:41:15,929 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 16:41:15,929 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 16:41:15,938 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 16:41:15,938 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1734935374] [2022-04-06 16:41:15,938 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 16:41:15,938 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 16:41:15,938 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 16:41:15,939 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 16:41:15,968 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 16:41:16,001 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 16:41:16,001 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 16:41:16,002 INFO L263 TraceCheckSpWp]: Trace formula consists of 149 conjuncts, 22 conjunts are in the unsatisfiable core [2022-04-06 16:41:16,003 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 16:41:16,165 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-04-06 16:41:16,166 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 16:41:16,258 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-06 16:41:16,259 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 16:41:16,259 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [513068431] [2022-04-06 16:41:16,259 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 16:41:16,259 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1734935374] [2022-04-06 16:41:16,259 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1734935374] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 16:41:16,259 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 16:41:16,259 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 6] total 11 [2022-04-06 16:41:16,261 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 16:41:16,261 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1028963858] [2022-04-06 16:41:16,261 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1028963858] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 16:41:16,261 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 16:41:16,261 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-04-06 16:41:16,261 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1776651745] [2022-04-06 16:41:16,261 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 16:41:16,263 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-06 16:41:16,263 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:16,263 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-06 16:41:16,263 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2022-04-06 16:41:16,263 INFO L87 Difference]: Start difference. First operand 109 states and 147 transitions. Second operand has 9 states, 9 states have (on average 3.111111111111111) internal successors, (28), 7 states have internal predecessors, (28), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-06 16:41:16,362 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 16:41:16,363 INFO L93 Difference]: Finished difference Result 154 states and 208 transitions. [2022-04-06 16:41:16,363 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-06 16:41:16,363 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 3.111111111111111) internal successors, (28), 7 states have internal predecessors, (28), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 36 [2022-04-06 16:41:16,363 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 16:41:16,364 INFO L225 Difference]: With dead ends: 154 [2022-04-06 16:41:16,364 INFO L226 Difference]: Without dead ends: 152 [2022-04-06 16:41:16,364 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 61 SyntacticMatches, 1 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=31, Invalid=125, Unknown=0, NotChecked=0, Total=156 [2022-04-06 16:41:16,366 INFO L913 BasicCegarLoop]: 64 mSDtfsCounter, 66 mSDsluCounter, 249 mSDsCounter, 0 mSdLazyCounter, 154 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 78 SdHoareTripleChecker+Valid, 313 SdHoareTripleChecker+Invalid, 165 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 154 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 16:41:16,366 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [78 Valid, 313 Invalid, 165 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 154 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 16:41:16,367 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 152 states. [2022-04-06 16:41:16,383 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 152 to 148. [2022-04-06 16:41:16,384 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 148 states, 109 states have (on average 1.3394495412844036) internal successors, (146), 110 states have internal predecessors, (146), 29 states have call successors, (29), 10 states have call predecessors, (29), 9 states have return successors, (27), 27 states have call predecessors, (27), 27 states have call successors, (27) [2022-04-06 16:41:16,385 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 148 states to 148 states and 202 transitions. [2022-04-06 16:41:16,385 INFO L78 Accepts]: Start accepts. Automaton has 148 states and 202 transitions. Word has length 36 [2022-04-06 16:41:16,386 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 16:41:16,386 INFO L478 AbstractCegarLoop]: Abstraction has 148 states and 202 transitions. [2022-04-06 16:41:16,386 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 3.111111111111111) internal successors, (28), 7 states have internal predecessors, (28), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-06 16:41:16,386 INFO L276 IsEmpty]: Start isEmpty. Operand 148 states and 202 transitions. [2022-04-06 16:41:16,386 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2022-04-06 16:41:16,386 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 16:41:16,387 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 16:41:16,405 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2022-04-06 16:41:16,603 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2022-04-06 16:41:16,603 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 16:41:16,603 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 16:41:16,604 INFO L85 PathProgramCache]: Analyzing trace with hash -428189223, now seen corresponding path program 3 times [2022-04-06 16:41:16,604 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:16,604 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1761074763] [2022-04-06 16:41:16,604 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 16:41:16,604 INFO L85 PathProgramCache]: Analyzing trace with hash -428189223, now seen corresponding path program 4 times [2022-04-06 16:41:16,604 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 16:41:16,604 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1795579601] [2022-04-06 16:41:16,604 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 16:41:16,604 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 16:41:16,622 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 16:41:16,622 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [690362808] [2022-04-06 16:41:16,623 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-06 16:41:16,623 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 16:41:16,623 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 16:41:16,627 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 16:41:16,643 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2022-04-06 16:41:16,679 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-06 16:41:16,679 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 16:41:16,680 INFO L263 TraceCheckSpWp]: Trace formula consists of 126 conjuncts, 5 conjunts are in the unsatisfiable core [2022-04-06 16:41:16,683 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 16:41:16,732 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 11 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-06 16:41:16,732 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 16:41:16,732 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 16:41:16,732 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1795579601] [2022-04-06 16:41:16,732 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 16:41:16,732 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [690362808] [2022-04-06 16:41:16,733 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [690362808] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 16:41:16,733 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 16:41:16,733 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 16:41:16,733 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 16:41:16,733 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1761074763] [2022-04-06 16:41:16,733 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1761074763] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 16:41:16,733 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 16:41:16,733 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 16:41:16,733 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2079333435] [2022-04-06 16:41:16,733 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 16:41:16,733 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 16:41:16,734 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:16,734 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 16:41:16,734 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-06 16:41:16,734 INFO L87 Difference]: Start difference. First operand 148 states and 202 transitions. Second operand has 5 states, 5 states have (on average 5.2) internal successors, (26), 5 states have internal predecessors, (26), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-06 16:41:16,833 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 16:41:16,833 INFO L93 Difference]: Finished difference Result 300 states and 442 transitions. [2022-04-06 16:41:16,834 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-06 16:41:16,834 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.2) internal successors, (26), 5 states have internal predecessors, (26), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 37 [2022-04-06 16:41:16,834 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 16:41:16,835 INFO L225 Difference]: With dead ends: 300 [2022-04-06 16:41:16,835 INFO L226 Difference]: Without dead ends: 249 [2022-04-06 16:41:16,835 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 34 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2022-04-06 16:41:16,836 INFO L913 BasicCegarLoop]: 64 mSDtfsCounter, 29 mSDsluCounter, 112 mSDsCounter, 0 mSdLazyCounter, 92 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 176 SdHoareTripleChecker+Invalid, 101 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 92 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 16:41:16,836 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [33 Valid, 176 Invalid, 101 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 92 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 16:41:16,836 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 249 states. [2022-04-06 16:41:16,850 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 249 to 175. [2022-04-06 16:41:16,850 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 175 states, 136 states have (on average 1.3455882352941178) internal successors, (183), 137 states have internal predecessors, (183), 29 states have call successors, (29), 10 states have call predecessors, (29), 9 states have return successors, (27), 27 states have call predecessors, (27), 27 states have call successors, (27) [2022-04-06 16:41:16,851 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 175 states to 175 states and 239 transitions. [2022-04-06 16:41:16,851 INFO L78 Accepts]: Start accepts. Automaton has 175 states and 239 transitions. Word has length 37 [2022-04-06 16:41:16,852 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 16:41:16,852 INFO L478 AbstractCegarLoop]: Abstraction has 175 states and 239 transitions. [2022-04-06 16:41:16,852 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.2) internal successors, (26), 5 states have internal predecessors, (26), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-06 16:41:16,852 INFO L276 IsEmpty]: Start isEmpty. Operand 175 states and 239 transitions. [2022-04-06 16:41:16,852 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2022-04-06 16:41:16,852 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 16:41:16,852 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 16:41:16,870 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2022-04-06 16:41:17,068 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2022-04-06 16:41:17,069 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 16:41:17,069 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 16:41:17,069 INFO L85 PathProgramCache]: Analyzing trace with hash -957710478, now seen corresponding path program 1 times [2022-04-06 16:41:17,069 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:17,069 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1530257241] [2022-04-06 16:41:17,069 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 16:41:17,069 INFO L85 PathProgramCache]: Analyzing trace with hash -957710478, now seen corresponding path program 2 times [2022-04-06 16:41:17,070 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 16:41:17,070 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [867061785] [2022-04-06 16:41:17,070 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 16:41:17,070 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 16:41:17,077 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 16:41:17,077 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [143095179] [2022-04-06 16:41:17,078 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 16:41:17,078 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 16:41:17,078 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 16:41:17,081 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 16:41:17,093 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2022-04-06 16:41:17,116 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 16:41:17,116 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 16:41:17,116 INFO L263 TraceCheckSpWp]: Trace formula consists of 137 conjuncts, 13 conjunts are in the unsatisfiable core [2022-04-06 16:41:17,120 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 16:41:17,218 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 7 proven. 0 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2022-04-06 16:41:17,219 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 16:41:17,219 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 16:41:17,219 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [867061785] [2022-04-06 16:41:17,219 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 16:41:17,219 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [143095179] [2022-04-06 16:41:17,219 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [143095179] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 16:41:17,219 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 16:41:17,219 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-04-06 16:41:17,219 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 16:41:17,220 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1530257241] [2022-04-06 16:41:17,220 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1530257241] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 16:41:17,220 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 16:41:17,220 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-04-06 16:41:17,220 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [976796481] [2022-04-06 16:41:17,220 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 16:41:17,220 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-06 16:41:17,220 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:17,221 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-06 16:41:17,221 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=56, Unknown=0, NotChecked=0, Total=72 [2022-04-06 16:41:17,221 INFO L87 Difference]: Start difference. First operand 175 states and 239 transitions. Second operand has 9 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 7 states have internal predecessors, (24), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 3 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-06 16:41:17,327 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 16:41:17,327 INFO L93 Difference]: Finished difference Result 193 states and 262 transitions. [2022-04-06 16:41:17,327 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-06 16:41:17,327 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 7 states have internal predecessors, (24), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 3 states have call predecessors, (5), 2 states have call successors, (5) Word has length 39 [2022-04-06 16:41:17,328 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 16:41:17,329 INFO L225 Difference]: With dead ends: 193 [2022-04-06 16:41:17,329 INFO L226 Difference]: Without dead ends: 191 [2022-04-06 16:41:17,329 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 31 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=34, Invalid=122, Unknown=0, NotChecked=0, Total=156 [2022-04-06 16:41:17,329 INFO L913 BasicCegarLoop]: 45 mSDtfsCounter, 61 mSDsluCounter, 199 mSDsCounter, 0 mSdLazyCounter, 131 mSolverCounterSat, 20 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 65 SdHoareTripleChecker+Valid, 244 SdHoareTripleChecker+Invalid, 151 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 20 IncrementalHoareTripleChecker+Valid, 131 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 16:41:17,330 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [65 Valid, 244 Invalid, 151 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [20 Valid, 131 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 16:41:17,330 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 191 states. [2022-04-06 16:41:17,346 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 191 to 190. [2022-04-06 16:41:17,347 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 190 states, 145 states have (on average 1.3379310344827586) internal successors, (194), 146 states have internal predecessors, (194), 33 states have call successors, (33), 12 states have call predecessors, (33), 11 states have return successors, (31), 31 states have call predecessors, (31), 31 states have call successors, (31) [2022-04-06 16:41:17,347 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 190 states to 190 states and 258 transitions. [2022-04-06 16:41:17,348 INFO L78 Accepts]: Start accepts. Automaton has 190 states and 258 transitions. Word has length 39 [2022-04-06 16:41:17,349 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 16:41:17,349 INFO L478 AbstractCegarLoop]: Abstraction has 190 states and 258 transitions. [2022-04-06 16:41:17,349 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 7 states have internal predecessors, (24), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 3 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-06 16:41:17,349 INFO L276 IsEmpty]: Start isEmpty. Operand 190 states and 258 transitions. [2022-04-06 16:41:17,350 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2022-04-06 16:41:17,350 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 16:41:17,350 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 16:41:17,376 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2022-04-06 16:41:17,565 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2022-04-06 16:41:17,565 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 16:41:17,566 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 16:41:17,566 INFO L85 PathProgramCache]: Analyzing trace with hash 409018142, now seen corresponding path program 1 times [2022-04-06 16:41:17,566 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:17,566 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [557639583] [2022-04-06 16:41:17,566 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 16:41:17,566 INFO L85 PathProgramCache]: Analyzing trace with hash 409018142, now seen corresponding path program 2 times [2022-04-06 16:41:17,566 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 16:41:17,567 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [694493894] [2022-04-06 16:41:17,567 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 16:41:17,567 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 16:41:17,574 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 16:41:17,574 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1880555950] [2022-04-06 16:41:17,574 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 16:41:17,574 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 16:41:17,574 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 16:41:17,575 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 16:41:17,579 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2022-04-06 16:41:17,621 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 16:41:17,621 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 16:41:17,622 INFO L263 TraceCheckSpWp]: Trace formula consists of 158 conjuncts, 37 conjunts are in the unsatisfiable core [2022-04-06 16:41:17,623 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 16:41:17,867 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 2 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-06 16:41:17,867 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 16:41:17,987 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 2 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-06 16:41:17,987 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 16:41:17,987 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [694493894] [2022-04-06 16:41:17,987 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 16:41:17,987 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1880555950] [2022-04-06 16:41:17,987 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1880555950] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 16:41:17,987 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 16:41:17,988 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 7] total 14 [2022-04-06 16:41:17,988 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 16:41:17,988 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [557639583] [2022-04-06 16:41:17,988 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [557639583] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 16:41:17,988 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 16:41:17,988 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2022-04-06 16:41:17,988 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1384258957] [2022-04-06 16:41:17,988 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 16:41:17,988 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-04-06 16:41:17,988 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:17,989 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-04-06 16:41:17,989 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=147, Unknown=0, NotChecked=0, Total=182 [2022-04-06 16:41:17,989 INFO L87 Difference]: Start difference. First operand 190 states and 258 transitions. Second operand has 11 states, 10 states have (on average 2.8) internal successors, (28), 8 states have internal predecessors, (28), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2022-04-06 16:41:18,154 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 16:41:18,155 INFO L93 Difference]: Finished difference Result 199 states and 266 transitions. [2022-04-06 16:41:18,155 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-04-06 16:41:18,155 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 2.8) internal successors, (28), 8 states have internal predecessors, (28), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) Word has length 41 [2022-04-06 16:41:18,155 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 16:41:18,156 INFO L225 Difference]: With dead ends: 199 [2022-04-06 16:41:18,156 INFO L226 Difference]: Without dead ends: 197 [2022-04-06 16:41:18,157 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 84 GetRequests, 68 SyntacticMatches, 1 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 38 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=51, Invalid=221, Unknown=0, NotChecked=0, Total=272 [2022-04-06 16:41:18,157 INFO L913 BasicCegarLoop]: 55 mSDtfsCounter, 114 mSDsluCounter, 244 mSDsCounter, 0 mSdLazyCounter, 233 mSolverCounterSat, 38 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 126 SdHoareTripleChecker+Valid, 299 SdHoareTripleChecker+Invalid, 271 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 38 IncrementalHoareTripleChecker+Valid, 233 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 16:41:18,157 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [126 Valid, 299 Invalid, 271 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [38 Valid, 233 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 16:41:18,157 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 197 states. [2022-04-06 16:41:18,175 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 197 to 194. [2022-04-06 16:41:18,176 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 194 states, 148 states have (on average 1.3310810810810811) internal successors, (197), 149 states have internal predecessors, (197), 33 states have call successors, (33), 13 states have call predecessors, (33), 12 states have return successors, (31), 31 states have call predecessors, (31), 31 states have call successors, (31) [2022-04-06 16:41:18,177 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 194 states to 194 states and 261 transitions. [2022-04-06 16:41:18,177 INFO L78 Accepts]: Start accepts. Automaton has 194 states and 261 transitions. Word has length 41 [2022-04-06 16:41:18,178 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 16:41:18,178 INFO L478 AbstractCegarLoop]: Abstraction has 194 states and 261 transitions. [2022-04-06 16:41:18,178 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 2.8) internal successors, (28), 8 states have internal predecessors, (28), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2022-04-06 16:41:18,178 INFO L276 IsEmpty]: Start isEmpty. Operand 194 states and 261 transitions. [2022-04-06 16:41:18,179 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2022-04-06 16:41:18,179 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 16:41:18,179 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 16:41:18,207 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2022-04-06 16:41:18,395 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2022-04-06 16:41:18,395 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 16:41:18,395 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 16:41:18,395 INFO L85 PathProgramCache]: Analyzing trace with hash -1943393983, now seen corresponding path program 1 times [2022-04-06 16:41:18,396 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:18,396 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [117954647] [2022-04-06 16:41:18,396 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 16:41:18,396 INFO L85 PathProgramCache]: Analyzing trace with hash -1943393983, now seen corresponding path program 2 times [2022-04-06 16:41:18,396 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 16:41:18,397 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [271487414] [2022-04-06 16:41:18,397 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 16:41:18,397 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 16:41:18,418 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 16:41:18,418 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1707355352] [2022-04-06 16:41:18,418 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 16:41:18,418 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 16:41:18,419 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 16:41:18,429 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 16:41:18,457 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2022-04-06 16:41:18,465 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 16:41:18,465 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 16:41:18,466 INFO L263 TraceCheckSpWp]: Trace formula consists of 146 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-06 16:41:18,466 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 16:41:18,530 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2022-04-06 16:41:18,531 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 16:41:18,531 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 16:41:18,531 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [271487414] [2022-04-06 16:41:18,531 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 16:41:18,531 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1707355352] [2022-04-06 16:41:18,531 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1707355352] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 16:41:18,531 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 16:41:18,531 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 16:41:18,531 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 16:41:18,531 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [117954647] [2022-04-06 16:41:18,531 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [117954647] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 16:41:18,531 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 16:41:18,532 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 16:41:18,532 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1527540838] [2022-04-06 16:41:18,532 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 16:41:18,532 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 16:41:18,532 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:18,532 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 16:41:18,532 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-06 16:41:18,532 INFO L87 Difference]: Start difference. First operand 194 states and 261 transitions. Second operand has 5 states, 5 states have (on average 4.2) internal successors, (21), 4 states have internal predecessors, (21), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2022-04-06 16:41:18,579 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 16:41:18,579 INFO L93 Difference]: Finished difference Result 261 states and 367 transitions. [2022-04-06 16:41:18,579 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 16:41:18,579 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.2) internal successors, (21), 4 states have internal predecessors, (21), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 44 [2022-04-06 16:41:18,579 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 16:41:18,582 INFO L225 Difference]: With dead ends: 261 [2022-04-06 16:41:18,582 INFO L226 Difference]: Without dead ends: 259 [2022-04-06 16:41:18,582 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 44 GetRequests, 40 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 16:41:18,583 INFO L913 BasicCegarLoop]: 48 mSDtfsCounter, 12 mSDsluCounter, 115 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 163 SdHoareTripleChecker+Invalid, 50 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 16:41:18,583 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [13 Valid, 163 Invalid, 50 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 16:41:18,583 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 259 states. [2022-04-06 16:41:18,603 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 259 to 228. [2022-04-06 16:41:18,604 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 228 states, 161 states have (on average 1.329192546583851) internal successors, (214), 167 states have internal predecessors, (214), 53 states have call successors, (53), 14 states have call predecessors, (53), 13 states have return successors, (51), 46 states have call predecessors, (51), 51 states have call successors, (51) [2022-04-06 16:41:18,605 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 228 states to 228 states and 318 transitions. [2022-04-06 16:41:18,606 INFO L78 Accepts]: Start accepts. Automaton has 228 states and 318 transitions. Word has length 44 [2022-04-06 16:41:18,607 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 16:41:18,607 INFO L478 AbstractCegarLoop]: Abstraction has 228 states and 318 transitions. [2022-04-06 16:41:18,607 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.2) internal successors, (21), 4 states have internal predecessors, (21), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2022-04-06 16:41:18,607 INFO L276 IsEmpty]: Start isEmpty. Operand 228 states and 318 transitions. [2022-04-06 16:41:18,607 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2022-04-06 16:41:18,607 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 16:41:18,607 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 16:41:18,641 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2022-04-06 16:41:18,824 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2022-04-06 16:41:18,824 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 16:41:18,824 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 16:41:18,824 INFO L85 PathProgramCache]: Analyzing trace with hash -772903697, now seen corresponding path program 1 times [2022-04-06 16:41:18,824 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:18,824 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1605847247] [2022-04-06 16:41:18,825 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 16:41:18,825 INFO L85 PathProgramCache]: Analyzing trace with hash -772903697, now seen corresponding path program 2 times [2022-04-06 16:41:18,825 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 16:41:18,825 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2030353298] [2022-04-06 16:41:18,825 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 16:41:18,825 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 16:41:18,831 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 16:41:18,831 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [366234884] [2022-04-06 16:41:18,831 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 16:41:18,831 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 16:41:18,832 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 16:41:18,847 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 16:41:18,848 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2022-04-06 16:41:18,913 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 16:41:18,913 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 16:41:18,914 INFO L263 TraceCheckSpWp]: Trace formula consists of 177 conjuncts, 13 conjunts are in the unsatisfiable core [2022-04-06 16:41:18,915 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 16:41:18,997 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 9 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-06 16:41:18,997 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 16:41:19,069 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 9 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-06 16:41:19,069 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 16:41:19,070 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2030353298] [2022-04-06 16:41:19,070 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 16:41:19,070 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [366234884] [2022-04-06 16:41:19,070 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [366234884] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 16:41:19,070 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 16:41:19,070 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 8 [2022-04-06 16:41:19,070 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 16:41:19,070 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1605847247] [2022-04-06 16:41:19,070 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1605847247] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 16:41:19,070 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 16:41:19,070 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-04-06 16:41:19,070 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1028309601] [2022-04-06 16:41:19,070 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 16:41:19,071 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-04-06 16:41:19,071 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:19,071 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-04-06 16:41:19,071 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=33, Unknown=0, NotChecked=0, Total=56 [2022-04-06 16:41:19,071 INFO L87 Difference]: Start difference. First operand 228 states and 318 transitions. Second operand has 8 states, 8 states have (on average 3.875) internal successors, (31), 7 states have internal predecessors, (31), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-06 16:41:19,139 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 16:41:19,139 INFO L93 Difference]: Finished difference Result 429 states and 607 transitions. [2022-04-06 16:41:19,139 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-04-06 16:41:19,139 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.875) internal successors, (31), 7 states have internal predecessors, (31), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) Word has length 42 [2022-04-06 16:41:19,139 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 16:41:19,141 INFO L225 Difference]: With dead ends: 429 [2022-04-06 16:41:19,141 INFO L226 Difference]: Without dead ends: 264 [2022-04-06 16:41:19,142 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 85 GetRequests, 76 SyntacticMatches, 1 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2022-04-06 16:41:19,142 INFO L913 BasicCegarLoop]: 51 mSDtfsCounter, 55 mSDsluCounter, 146 mSDsCounter, 0 mSdLazyCounter, 63 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 55 SdHoareTripleChecker+Valid, 197 SdHoareTripleChecker+Invalid, 85 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 63 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 16:41:19,142 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [55 Valid, 197 Invalid, 85 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 63 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 16:41:19,143 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 264 states. [2022-04-06 16:41:19,177 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 264 to 258. [2022-04-06 16:41:19,177 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 258 states, 183 states have (on average 1.3060109289617485) internal successors, (239), 189 states have internal predecessors, (239), 57 states have call successors, (57), 18 states have call predecessors, (57), 17 states have return successors, (55), 50 states have call predecessors, (55), 55 states have call successors, (55) [2022-04-06 16:41:19,178 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 258 states to 258 states and 351 transitions. [2022-04-06 16:41:19,179 INFO L78 Accepts]: Start accepts. Automaton has 258 states and 351 transitions. Word has length 42 [2022-04-06 16:41:19,179 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 16:41:19,179 INFO L478 AbstractCegarLoop]: Abstraction has 258 states and 351 transitions. [2022-04-06 16:41:19,179 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.875) internal successors, (31), 7 states have internal predecessors, (31), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-06 16:41:19,179 INFO L276 IsEmpty]: Start isEmpty. Operand 258 states and 351 transitions. [2022-04-06 16:41:19,179 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2022-04-06 16:41:19,179 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 16:41:19,180 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 16:41:19,196 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2022-04-06 16:41:19,395 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2022-04-06 16:41:19,396 INFO L403 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 16:41:19,396 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 16:41:19,396 INFO L85 PathProgramCache]: Analyzing trace with hash 744709461, now seen corresponding path program 1 times [2022-04-06 16:41:19,396 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:19,396 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1229477104] [2022-04-06 16:41:19,396 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 16:41:19,397 INFO L85 PathProgramCache]: Analyzing trace with hash 744709461, now seen corresponding path program 2 times [2022-04-06 16:41:19,397 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 16:41:19,397 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [715386819] [2022-04-06 16:41:19,397 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 16:41:19,397 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 16:41:19,403 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 16:41:19,403 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2071459952] [2022-04-06 16:41:19,403 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 16:41:19,403 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 16:41:19,404 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 16:41:19,404 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 16:41:19,406 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2022-04-06 16:41:19,448 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 16:41:19,448 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 16:41:19,449 INFO L263 TraceCheckSpWp]: Trace formula consists of 167 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-06 16:41:19,450 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 16:41:19,516 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 7 proven. 0 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2022-04-06 16:41:19,516 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 16:41:19,517 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 16:41:19,517 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [715386819] [2022-04-06 16:41:19,517 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 16:41:19,517 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2071459952] [2022-04-06 16:41:19,517 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2071459952] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 16:41:19,517 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 16:41:19,517 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 16:41:19,517 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 16:41:19,517 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1229477104] [2022-04-06 16:41:19,518 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1229477104] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 16:41:19,518 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 16:41:19,518 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 16:41:19,518 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [406603143] [2022-04-06 16:41:19,518 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 16:41:19,518 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 16:41:19,518 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:19,518 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 16:41:19,519 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-06 16:41:19,519 INFO L87 Difference]: Start difference. First operand 258 states and 351 transitions. Second operand has 5 states, 5 states have (on average 5.2) internal successors, (26), 4 states have internal predecessors, (26), 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 16:41:19,573 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 16:41:19,573 INFO L93 Difference]: Finished difference Result 332 states and 473 transitions. [2022-04-06 16:41:19,573 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 16:41:19,573 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.2) internal successors, (26), 4 states have internal predecessors, (26), 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 46 [2022-04-06 16:41:19,573 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 16:41:19,575 INFO L225 Difference]: With dead ends: 332 [2022-04-06 16:41:19,575 INFO L226 Difference]: Without dead ends: 330 [2022-04-06 16:41:19,575 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 42 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 16:41:19,576 INFO L913 BasicCegarLoop]: 44 mSDtfsCounter, 10 mSDsluCounter, 109 mSDsCounter, 0 mSdLazyCounter, 47 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 153 SdHoareTripleChecker+Invalid, 47 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 47 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 16:41:19,576 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 153 Invalid, 47 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 47 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 16:41:19,576 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 330 states. [2022-04-06 16:41:19,602 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 330 to 321. [2022-04-06 16:41:19,603 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 321 states, 213 states have (on average 1.3427230046948357) internal successors, (286), 223 states have internal predecessors, (286), 89 states have call successors, (89), 19 states have call predecessors, (89), 18 states have return successors, (87), 78 states have call predecessors, (87), 87 states have call successors, (87) [2022-04-06 16:41:19,604 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 321 states to 321 states and 462 transitions. [2022-04-06 16:41:19,604 INFO L78 Accepts]: Start accepts. Automaton has 321 states and 462 transitions. Word has length 46 [2022-04-06 16:41:19,604 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 16:41:19,604 INFO L478 AbstractCegarLoop]: Abstraction has 321 states and 462 transitions. [2022-04-06 16:41:19,605 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.2) internal successors, (26), 4 states have internal predecessors, (26), 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 16:41:19,605 INFO L276 IsEmpty]: Start isEmpty. Operand 321 states and 462 transitions. [2022-04-06 16:41:19,605 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2022-04-06 16:41:19,605 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 16:41:19,605 INFO L499 BasicCegarLoop]: trace histogram [5, 4, 4, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 16:41:19,634 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2022-04-06 16:41:19,821 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 16:41:19,822 INFO L403 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 16:41:19,822 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 16:41:19,822 INFO L85 PathProgramCache]: Analyzing trace with hash -522797827, now seen corresponding path program 1 times [2022-04-06 16:41:19,822 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:19,822 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [106326606] [2022-04-06 16:41:19,822 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 16:41:19,822 INFO L85 PathProgramCache]: Analyzing trace with hash -522797827, now seen corresponding path program 2 times [2022-04-06 16:41:19,823 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 16:41:19,823 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1529982479] [2022-04-06 16:41:19,823 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 16:41:19,823 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 16:41:19,829 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 16:41:19,829 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [53310758] [2022-04-06 16:41:19,829 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 16:41:19,829 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 16:41:19,829 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 16:41:19,830 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 16:41:19,831 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2022-04-06 16:41:19,866 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 16:41:19,867 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 16:41:19,867 INFO L263 TraceCheckSpWp]: Trace formula consists of 185 conjuncts, 13 conjunts are in the unsatisfiable core [2022-04-06 16:41:19,869 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 16:41:19,961 INFO L134 CoverageAnalysis]: Checked inductivity of 41 backedges. 8 proven. 5 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2022-04-06 16:41:19,961 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 16:41:20,049 INFO L134 CoverageAnalysis]: Checked inductivity of 41 backedges. 8 proven. 5 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2022-04-06 16:41:20,049 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 16:41:20,049 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1529982479] [2022-04-06 16:41:20,049 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 16:41:20,049 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [53310758] [2022-04-06 16:41:20,049 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [53310758] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 16:41:20,049 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 16:41:20,049 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 8 [2022-04-06 16:41:20,049 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 16:41:20,050 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [106326606] [2022-04-06 16:41:20,050 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [106326606] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 16:41:20,050 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 16:41:20,050 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-04-06 16:41:20,050 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2052061955] [2022-04-06 16:41:20,050 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 16:41:20,050 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-04-06 16:41:20,050 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:20,050 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-04-06 16:41:20,050 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=33, Unknown=0, NotChecked=0, Total=56 [2022-04-06 16:41:20,051 INFO L87 Difference]: Start difference. First operand 321 states and 462 transitions. Second operand has 8 states, 8 states have (on average 3.625) internal successors, (29), 7 states have internal predecessors, (29), 4 states have call successors, (9), 4 states have call predecessors, (9), 2 states have return successors, (7), 2 states have call predecessors, (7), 3 states have call successors, (7) [2022-04-06 16:41:20,141 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 16:41:20,141 INFO L93 Difference]: Finished difference Result 335 states and 475 transitions. [2022-04-06 16:41:20,141 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-04-06 16:41:20,142 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.625) internal successors, (29), 7 states have internal predecessors, (29), 4 states have call successors, (9), 4 states have call predecessors, (9), 2 states have return successors, (7), 2 states have call predecessors, (7), 3 states have call successors, (7) Word has length 57 [2022-04-06 16:41:20,142 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 16:41:20,143 INFO L225 Difference]: With dead ends: 335 [2022-04-06 16:41:20,143 INFO L226 Difference]: Without dead ends: 328 [2022-04-06 16:41:20,144 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 115 GetRequests, 106 SyntacticMatches, 1 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=36, Invalid=54, Unknown=0, NotChecked=0, Total=90 [2022-04-06 16:41:20,144 INFO L913 BasicCegarLoop]: 51 mSDtfsCounter, 46 mSDsluCounter, 161 mSDsCounter, 0 mSdLazyCounter, 66 mSolverCounterSat, 31 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 46 SdHoareTripleChecker+Valid, 212 SdHoareTripleChecker+Invalid, 97 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 31 IncrementalHoareTripleChecker+Valid, 66 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 16:41:20,144 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [46 Valid, 212 Invalid, 97 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [31 Valid, 66 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 16:41:20,144 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 328 states. [2022-04-06 16:41:20,167 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 328 to 324. [2022-04-06 16:41:20,167 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 324 states, 216 states have (on average 1.337962962962963) internal successors, (289), 226 states have internal predecessors, (289), 89 states have call successors, (89), 19 states have call predecessors, (89), 18 states have return successors, (87), 78 states have call predecessors, (87), 87 states have call successors, (87) [2022-04-06 16:41:20,168 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 324 states to 324 states and 465 transitions. [2022-04-06 16:41:20,168 INFO L78 Accepts]: Start accepts. Automaton has 324 states and 465 transitions. Word has length 57 [2022-04-06 16:41:20,169 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 16:41:20,169 INFO L478 AbstractCegarLoop]: Abstraction has 324 states and 465 transitions. [2022-04-06 16:41:20,169 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.625) internal successors, (29), 7 states have internal predecessors, (29), 4 states have call successors, (9), 4 states have call predecessors, (9), 2 states have return successors, (7), 2 states have call predecessors, (7), 3 states have call successors, (7) [2022-04-06 16:41:20,169 INFO L276 IsEmpty]: Start isEmpty. Operand 324 states and 465 transitions. [2022-04-06 16:41:20,169 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2022-04-06 16:41:20,169 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 16:41:20,169 INFO L499 BasicCegarLoop]: trace histogram [5, 4, 4, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 16:41:20,201 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2022-04-06 16:41:20,382 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2022-04-06 16:41:20,382 INFO L403 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 16:41:20,383 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 16:41:20,383 INFO L85 PathProgramCache]: Analyzing trace with hash 958119025, now seen corresponding path program 1 times [2022-04-06 16:41:20,383 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:20,383 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [2069886811] [2022-04-06 16:41:20,383 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 16:41:20,383 INFO L85 PathProgramCache]: Analyzing trace with hash 958119025, now seen corresponding path program 2 times [2022-04-06 16:41:20,383 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 16:41:20,383 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2058731894] [2022-04-06 16:41:20,383 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 16:41:20,383 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 16:41:20,389 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 16:41:20,389 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [501699473] [2022-04-06 16:41:20,390 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 16:41:20,390 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 16:41:20,390 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 16:41:20,394 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 16:41:20,403 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2022-04-06 16:41:20,441 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 16:41:20,441 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 16:41:20,442 INFO L263 TraceCheckSpWp]: Trace formula consists of 187 conjuncts, 52 conjunts are in the unsatisfiable core [2022-04-06 16:41:20,444 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 16:41:21,018 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 7 proven. 16 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2022-04-06 16:41:21,018 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 16:41:21,674 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 7 proven. 16 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2022-04-06 16:41:21,675 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 16:41:21,675 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2058731894] [2022-04-06 16:41:21,675 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 16:41:21,675 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [501699473] [2022-04-06 16:41:21,675 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [501699473] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 16:41:21,675 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 16:41:21,675 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 21 [2022-04-06 16:41:21,675 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 16:41:21,675 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [2069886811] [2022-04-06 16:41:21,675 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [2069886811] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 16:41:21,676 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 16:41:21,676 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [] total 13 [2022-04-06 16:41:21,676 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2015309286] [2022-04-06 16:41:21,676 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 16:41:21,676 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-04-06 16:41:21,676 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:21,676 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-04-06 16:41:21,677 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=73, Invalid=347, Unknown=0, NotChecked=0, Total=420 [2022-04-06 16:41:21,677 INFO L87 Difference]: Start difference. First operand 324 states and 465 transitions. Second operand has 13 states, 12 states have (on average 2.75) internal successors, (33), 12 states have internal predecessors, (33), 4 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 2 states have call predecessors, (7), 3 states have call successors, (7) [2022-04-06 16:41:22,093 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 16:41:22,093 INFO L93 Difference]: Finished difference Result 384 states and 559 transitions. [2022-04-06 16:41:22,093 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-04-06 16:41:22,093 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 2.75) internal successors, (33), 12 states have internal predecessors, (33), 4 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 2 states have call predecessors, (7), 3 states have call successors, (7) Word has length 58 [2022-04-06 16:41:22,094 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 16:41:22,095 INFO L225 Difference]: With dead ends: 384 [2022-04-06 16:41:22,095 INFO L226 Difference]: Without dead ends: 381 [2022-04-06 16:41:22,095 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 119 GetRequests, 95 SyntacticMatches, 1 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 95 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=101, Invalid=499, Unknown=0, NotChecked=0, Total=600 [2022-04-06 16:41:22,096 INFO L913 BasicCegarLoop]: 57 mSDtfsCounter, 65 mSDsluCounter, 385 mSDsCounter, 0 mSdLazyCounter, 595 mSolverCounterSat, 31 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 81 SdHoareTripleChecker+Valid, 442 SdHoareTripleChecker+Invalid, 626 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 31 IncrementalHoareTripleChecker+Valid, 595 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-04-06 16:41:22,096 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [81 Valid, 442 Invalid, 626 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [31 Valid, 595 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-04-06 16:41:22,096 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 381 states. [2022-04-06 16:41:22,123 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 381 to 377. [2022-04-06 16:41:22,123 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 377 states, 243 states have (on average 1.345679012345679) internal successors, (327), 256 states have internal predecessors, (327), 113 states have call successors, (113), 21 states have call predecessors, (113), 20 states have return successors, (111), 99 states have call predecessors, (111), 111 states have call successors, (111) [2022-04-06 16:41:22,125 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 377 states to 377 states and 551 transitions. [2022-04-06 16:41:22,125 INFO L78 Accepts]: Start accepts. Automaton has 377 states and 551 transitions. Word has length 58 [2022-04-06 16:41:22,125 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 16:41:22,125 INFO L478 AbstractCegarLoop]: Abstraction has 377 states and 551 transitions. [2022-04-06 16:41:22,125 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 2.75) internal successors, (33), 12 states have internal predecessors, (33), 4 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 2 states have call predecessors, (7), 3 states have call successors, (7) [2022-04-06 16:41:22,125 INFO L276 IsEmpty]: Start isEmpty. Operand 377 states and 551 transitions. [2022-04-06 16:41:22,126 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2022-04-06 16:41:22,126 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 16:41:22,126 INFO L499 BasicCegarLoop]: trace histogram [5, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 16:41:22,142 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2022-04-06 16:41:22,342 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2022-04-06 16:41:22,342 INFO L403 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 16:41:22,343 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 16:41:22,343 INFO L85 PathProgramCache]: Analyzing trace with hash 27973409, now seen corresponding path program 1 times [2022-04-06 16:41:22,343 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 16:41:22,343 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [216413371] [2022-04-06 16:41:22,343 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 16:41:22,343 INFO L85 PathProgramCache]: Analyzing trace with hash 27973409, now seen corresponding path program 2 times [2022-04-06 16:41:22,343 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 16:41:22,344 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1952751088] [2022-04-06 16:41:22,344 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 16:41:22,344 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 16:41:22,349 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 16:41:22,349 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [118474410] [2022-04-06 16:41:22,350 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 16:41:22,350 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 16:41:22,350 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 16:41:22,350 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 16:41:22,352 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2022-04-06 16:41:22,396 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 16:41:22,396 INFO L229 tOrderPrioritization]: Conjunction of SSA is sat [2022-04-06 16:41:22,396 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-04-06 16:41:22,410 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-04-06 16:41:22,432 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-04-06 16:41:22,433 INFO L130 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found a feasible trace [2022-04-06 16:41:22,433 INFO L618 BasicCegarLoop]: Counterexample is feasible [2022-04-06 16:41:22,434 INFO L788 garLoopResultBuilder]: Registering result UNSAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-04-06 16:41:22,452 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2022-04-06 16:41:22,651 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2022-04-06 16:41:22,654 INFO L719 BasicCegarLoop]: Path program histogram: [4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2] [2022-04-06 16:41:22,656 INFO L178 ceAbstractionStarter]: Computing trace abstraction results [2022-04-06 16:41:22,665 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 06.04 04:41:22 BoogieIcfgContainer [2022-04-06 16:41:22,665 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-04-06 16:41:22,666 INFO L158 Benchmark]: Toolchain (without parser) took 11019.43ms. Allocated memory was 181.4MB in the beginning and 286.3MB in the end (delta: 104.9MB). Free memory was 132.1MB in the beginning and 205.0MB in the end (delta: -72.9MB). Peak memory consumption was 31.0MB. Max. memory is 8.0GB. [2022-04-06 16:41:22,666 INFO L158 Benchmark]: CDTParser took 0.10ms. Allocated memory is still 181.4MB. Free memory is still 148.1MB. There was no memory consumed. Max. memory is 8.0GB. [2022-04-06 16:41:22,666 INFO L158 Benchmark]: CACSL2BoogieTranslator took 197.31ms. Allocated memory is still 181.4MB. Free memory was 132.0MB in the beginning and 157.3MB in the end (delta: -25.3MB). Peak memory consumption was 9.0MB. Max. memory is 8.0GB. [2022-04-06 16:41:22,666 INFO L158 Benchmark]: Boogie Preprocessor took 30.70ms. Allocated memory is still 181.4MB. Free memory was 157.3MB in the beginning and 155.9MB in the end (delta: 1.4MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-04-06 16:41:22,666 INFO L158 Benchmark]: RCFGBuilder took 241.49ms. Allocated memory is still 181.4MB. Free memory was 155.9MB in the beginning and 144.0MB in the end (delta: 11.9MB). Peak memory consumption was 12.6MB. Max. memory is 8.0GB. [2022-04-06 16:41:22,667 INFO L158 Benchmark]: TraceAbstraction took 10546.55ms. Allocated memory was 181.4MB in the beginning and 286.3MB in the end (delta: 104.9MB). Free memory was 143.6MB in the beginning and 205.0MB in the end (delta: -61.3MB). Peak memory consumption was 44.2MB. Max. memory is 8.0GB. [2022-04-06 16:41:22,667 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.10ms. Allocated memory is still 181.4MB. Free memory is still 148.1MB. There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 197.31ms. Allocated memory is still 181.4MB. Free memory was 132.0MB in the beginning and 157.3MB in the end (delta: -25.3MB). Peak memory consumption was 9.0MB. Max. memory is 8.0GB. * Boogie Preprocessor took 30.70ms. Allocated memory is still 181.4MB. Free memory was 157.3MB in the beginning and 155.9MB in the end (delta: 1.4MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * RCFGBuilder took 241.49ms. Allocated memory is still 181.4MB. Free memory was 155.9MB in the beginning and 144.0MB in the end (delta: 11.9MB). Peak memory consumption was 12.6MB. Max. memory is 8.0GB. * TraceAbstraction took 10546.55ms. Allocated memory was 181.4MB in the beginning and 286.3MB in the end (delta: 104.9MB). Free memory was 143.6MB in the beginning and 205.0MB in the end (delta: -61.3MB). Peak memory consumption was 44.2MB. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - CounterExampleResult [Line: 13]: a call to reach_error is reachable a call to reach_error is reachable We found a FailurePath: [L18] int counter = 0; [L20] int x, y; [L21] long long a, b, p, q, r, s; [L22] x = __VERIFIER_nondet_int() [L23] y = __VERIFIER_nondet_int() [L24] CALL assume_abort_if_not(x >= 1) [L8] COND FALSE !(!cond) [L24] RET assume_abort_if_not(x >= 1) [L25] CALL assume_abort_if_not(y >= 1) [L8] COND FALSE !(!cond) [L25] RET assume_abort_if_not(y >= 1) [L27] a = x [L28] b = y [L29] p = 1 [L30] q = 0 [L31] r = 0 [L32] s = 1 [L34] EXPR counter++ [L34] COND TRUE counter++<5 [L35] COND FALSE !(!(b != 0)) [L37] long long c, k; [L38] c = a [L39] k = 0 [L41] EXPR counter++ [L41] COND TRUE counter++<5 [L42] COND TRUE !(c >= b) [L63] a = b [L64] b = c [L65] long long temp; [L66] temp = p [L67] p = q [L68] q = temp - q * k [L69] temp = r [L70] r = s [L71] s = temp - s * k [L34] EXPR counter++ [L34] COND TRUE counter++<5 [L35] COND FALSE !(!(b != 0)) [L37] long long c, k; [L38] c = a [L39] k = 0 [L41] EXPR counter++ [L41] COND TRUE counter++<5 [L42] COND FALSE !(!(c >= b)) [L44] long long d, v; [L45] d = 1 [L46] v = b [L48] EXPR counter++ [L48] COND TRUE counter++<5 [L49] CALL __VERIFIER_assert(a == y * r + x * p) [L11] COND FALSE !(!(cond)) [L49] RET __VERIFIER_assert(a == y * r + x * p) [L50] CALL __VERIFIER_assert(b == x * q + y * s) [L11] COND FALSE !(!(cond)) [L50] RET __VERIFIER_assert(b == x * q + y * s) [L51] CALL __VERIFIER_assert(a == k * b + c) [L11] COND FALSE !(!(cond)) [L51] RET __VERIFIER_assert(a == k * b + c) [L52] CALL __VERIFIER_assert(v == b * d) [L11] COND FALSE !(!(cond)) [L52] RET __VERIFIER_assert(v == b * d) [L54] COND TRUE !(c >= 2 * v) [L59] c = c - v [L60] k = k + d [L41] EXPR counter++ [L41] COND FALSE !(counter++<5) [L63] a = b [L64] b = c [L65] long long temp; [L66] temp = p [L67] p = q [L68] q = temp - q * k [L69] temp = r [L70] r = s [L71] s = temp - s * k [L34] EXPR counter++ [L34] COND FALSE !(counter++<5) [L73] CALL __VERIFIER_assert(p*x - q*x + r*y - s*y == a) [L11] COND TRUE !(cond) [L13] reach_error() - StatisticsResult: Ultimate Automizer benchmark data CFG has 6 procedures, 43 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 10.5s, OverallIterations: 18, TraceHistogramMax: 5, PathProgramHistogramMax: 4, EmptinessCheckTime: 0.0s, AutomataDifference: 1.8s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, PartialOrderReductionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 739 SdHoareTripleChecker+Valid, 1.0s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 678 mSDsluCounter, 3372 SdHoareTripleChecker+Invalid, 0.8s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 2525 mSDsCounter, 298 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1779 IncrementalHoareTripleChecker+Invalid, 2077 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 298 mSolverCounterUnsat, 847 mSDtfsCounter, 1779 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 966 GetRequests, 823 SyntacticMatches, 8 SemanticMatches, 135 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 214 ImplicationChecksByTransitivity, 0.8s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=377occurred in iteration=17, InterpolantAutomatonStates: 127, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.3s AutomataMinimizationTime, 17 MinimizatonAttempts, 185 StatesRemovedByMinimization, 14 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: No data available, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available RESULT: Ultimate proved your program to be incorrect! [2022-04-06 16:41:22,678 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Ended with exit code 0 Received shutdown request...