./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/combinations/gcd_4+newton_2_3.i --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 798a7b37 Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/combinations/gcd_4+newton_2_3.i -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash a8b52922fdfe93dd417523e4e63c80c50c6631dbe5ff22aa1a5e25c09a617278 --- Real Ultimate output --- This is Ultimate 0.3.0-?-798a7b3-m [2025-03-03 15:58:14,021 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-03 15:58:14,081 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-03 15:58:14,087 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-03 15:58:14,087 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-03 15:58:14,108 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-03 15:58:14,108 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-03 15:58:14,109 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-03 15:58:14,109 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-03 15:58:14,109 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-03 15:58:14,109 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-03 15:58:14,109 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-03 15:58:14,110 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-03 15:58:14,110 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-03 15:58:14,110 INFO L153 SettingsManager]: * Use SBE=true [2025-03-03 15:58:14,110 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-03 15:58:14,110 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-03 15:58:14,110 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-03 15:58:14,110 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-03 15:58:14,110 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-03 15:58:14,110 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-03 15:58:14,110 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-03 15:58:14,110 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-03 15:58:14,110 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-03 15:58:14,110 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-03 15:58:14,110 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-03 15:58:14,110 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-03 15:58:14,110 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-03 15:58:14,111 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-03 15:58:14,111 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-03 15:58:14,111 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-03 15:58:14,111 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-03 15:58:14,111 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 15:58:14,111 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-03 15:58:14,111 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-03 15:58:14,111 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-03 15:58:14,111 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-03 15:58:14,111 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-03 15:58:14,111 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-03 15:58:14,111 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-03 15:58:14,111 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-03 15:58:14,111 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-03 15:58:14,111 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-03 15:58:14,111 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> a8b52922fdfe93dd417523e4e63c80c50c6631dbe5ff22aa1a5e25c09a617278 [2025-03-03 15:58:14,346 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-03 15:58:14,353 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-03 15:58:14,356 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-03 15:58:14,357 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-03 15:58:14,357 INFO L274 PluginConnector]: CDTParser initialized [2025-03-03 15:58:14,359 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/combinations/gcd_4+newton_2_3.i [2025-03-03 15:58:15,502 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/fb1d02fc9/1a58cc9c40e4482c97f2f0e59cc576eb/FLAG808953ece [2025-03-03 15:58:15,711 INFO L384 CDTParser]: Found 1 translation units. [2025-03-03 15:58:15,712 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/combinations/gcd_4+newton_2_3.i [2025-03-03 15:58:15,717 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/fb1d02fc9/1a58cc9c40e4482c97f2f0e59cc576eb/FLAG808953ece [2025-03-03 15:58:16,079 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/fb1d02fc9/1a58cc9c40e4482c97f2f0e59cc576eb [2025-03-03 15:58:16,080 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-03 15:58:16,081 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-03 15:58:16,082 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-03 15:58:16,082 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-03 15:58:16,085 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-03 15:58:16,085 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 03:58:16" (1/1) ... [2025-03-03 15:58:16,087 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5c5c60b3 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:58:16, skipping insertion in model container [2025-03-03 15:58:16,087 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 03:58:16" (1/1) ... [2025-03-03 15:58:16,099 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-03 15:58:16,211 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/combinations/gcd_4+newton_2_3.i[1224,1237] [2025-03-03 15:58:16,228 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/combinations/gcd_4+newton_2_3.i[2827,2840] [2025-03-03 15:58:16,229 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 15:58:16,235 INFO L200 MainTranslator]: Completed pre-run [2025-03-03 15:58:16,248 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/combinations/gcd_4+newton_2_3.i[1224,1237] [2025-03-03 15:58:16,260 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/combinations/gcd_4+newton_2_3.i[2827,2840] [2025-03-03 15:58:16,261 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 15:58:16,280 INFO L204 MainTranslator]: Completed translation [2025-03-03 15:58:16,281 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:58:16 WrapperNode [2025-03-03 15:58:16,282 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-03 15:58:16,283 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-03 15:58:16,283 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-03 15:58:16,283 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-03 15:58:16,288 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:58:16" (1/1) ... [2025-03-03 15:58:16,294 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:58:16" (1/1) ... [2025-03-03 15:58:16,308 INFO L138 Inliner]: procedures = 27, calls = 26, calls flagged for inlining = 6, calls inlined = 6, statements flattened = 76 [2025-03-03 15:58:16,308 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-03 15:58:16,309 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-03 15:58:16,309 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-03 15:58:16,309 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-03 15:58:16,315 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:58:16" (1/1) ... [2025-03-03 15:58:16,315 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:58:16" (1/1) ... [2025-03-03 15:58:16,316 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:58:16" (1/1) ... [2025-03-03 15:58:16,329 INFO L175 MemorySlicer]: Split 10 memory accesses to 2 slices as follows [2, 8]. 80 percent of accesses are in the largest equivalence class. The 10 initializations are split as follows [2, 8]. The 0 writes are split as follows [0, 0]. [2025-03-03 15:58:16,330 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:58:16" (1/1) ... [2025-03-03 15:58:16,330 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:58:16" (1/1) ... [2025-03-03 15:58:16,333 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:58:16" (1/1) ... [2025-03-03 15:58:16,334 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:58:16" (1/1) ... [2025-03-03 15:58:16,336 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:58:16" (1/1) ... [2025-03-03 15:58:16,337 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:58:16" (1/1) ... [2025-03-03 15:58:16,338 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-03 15:58:16,338 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-03 15:58:16,338 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-03 15:58:16,338 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-03 15:58:16,339 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:58:16" (1/1) ... [2025-03-03 15:58:16,343 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 15:58:16,353 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 15:58:16,364 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2025-03-03 15:58:16,369 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2025-03-03 15:58:16,386 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-03 15:58:16,387 INFO L130 BoogieDeclarations]: Found specification of procedure fp [2025-03-03 15:58:16,387 INFO L138 BoogieDeclarations]: Found implementation of procedure fp [2025-03-03 15:58:16,387 INFO L130 BoogieDeclarations]: Found specification of procedure f [2025-03-03 15:58:16,387 INFO L138 BoogieDeclarations]: Found implementation of procedure f [2025-03-03 15:58:16,387 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-03 15:58:16,387 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2025-03-03 15:58:16,387 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-03 15:58:16,387 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-03 15:58:16,387 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-03-03 15:58:16,387 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-03-03 15:58:16,438 INFO L256 CfgBuilder]: Building ICFG [2025-03-03 15:58:16,440 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-03 15:58:16,577 INFO L? ?]: Removed 23 outVars from TransFormulas that were not future-live. [2025-03-03 15:58:16,579 INFO L307 CfgBuilder]: Performing block encoding [2025-03-03 15:58:16,587 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-03 15:58:16,588 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-03 15:58:16,588 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 03:58:16 BoogieIcfgContainer [2025-03-03 15:58:16,588 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-03 15:58:16,590 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-03 15:58:16,590 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-03 15:58:16,596 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-03 15:58:16,596 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 03.03 03:58:16" (1/3) ... [2025-03-03 15:58:16,597 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1015ffb8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 03:58:16, skipping insertion in model container [2025-03-03 15:58:16,597 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:58:16" (2/3) ... [2025-03-03 15:58:16,597 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1015ffb8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 03:58:16, skipping insertion in model container [2025-03-03 15:58:16,597 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 03:58:16" (3/3) ... [2025-03-03 15:58:16,598 INFO L128 eAbstractionObserver]: Analyzing ICFG gcd_4+newton_2_3.i [2025-03-03 15:58:16,611 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-03 15:58:16,612 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG gcd_4+newton_2_3.i that has 4 procedures, 42 locations, 1 initial locations, 1 loop locations, and 2 error locations. [2025-03-03 15:58:16,655 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-03 15:58:16,664 INFO L333 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopHeads, 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, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@71258632, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-03 15:58:16,664 INFO L334 AbstractCegarLoop]: Starting to check reachability of 2 error locations. [2025-03-03 15:58:16,667 INFO L276 IsEmpty]: Start isEmpty. Operand has 42 states, 29 states have (on average 1.3793103448275863) internal successors, (40), 31 states have internal predecessors, (40), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2025-03-03 15:58:16,673 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2025-03-03 15:58:16,673 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 15:58:16,674 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 15:58:16,674 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 15:58:16,678 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 15:58:16,678 INFO L85 PathProgramCache]: Analyzing trace with hash -1151646490, now seen corresponding path program 1 times [2025-03-03 15:58:16,684 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 15:58:16,684 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [796530111] [2025-03-03 15:58:16,684 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 15:58:16,685 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 15:58:16,751 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 11 statements into 1 equivalence classes. [2025-03-03 15:58:16,770 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 11 of 11 statements. [2025-03-03 15:58:16,771 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 15:58:16,771 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 15:58:16,897 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 15:58:16,898 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 15:58:16,898 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [796530111] [2025-03-03 15:58:16,901 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [796530111] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 15:58:16,901 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 15:58:16,901 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2025-03-03 15:58:16,903 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1079544758] [2025-03-03 15:58:16,903 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 15:58:16,905 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2025-03-03 15:58:16,906 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 15:58:16,919 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2025-03-03 15:58:16,919 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-03-03 15:58:16,921 INFO L87 Difference]: Start difference. First operand has 42 states, 29 states have (on average 1.3793103448275863) internal successors, (40), 31 states have internal predecessors, (40), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 15:58:16,963 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 15:58:16,963 INFO L93 Difference]: Finished difference Result 80 states and 105 transitions. [2025-03-03 15:58:16,964 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2025-03-03 15:58:16,965 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 11 [2025-03-03 15:58:16,965 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 15:58:16,969 INFO L225 Difference]: With dead ends: 80 [2025-03-03 15:58:16,969 INFO L226 Difference]: Without dead ends: 37 [2025-03-03 15:58:16,971 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-03-03 15:58:16,973 INFO L435 NwaCegarLoop]: 45 mSDtfsCounter, 5 mSDsluCounter, 39 mSDsCounter, 0 mSdLazyCounter, 11 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 84 SdHoareTripleChecker+Invalid, 12 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 11 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 15:58:16,973 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 84 Invalid, 12 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 11 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 15:58:16,984 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2025-03-03 15:58:16,995 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 37. [2025-03-03 15:58:16,996 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 25 states have (on average 1.28) internal successors, (32), 27 states have internal predecessors, (32), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-03-03 15:58:16,999 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 45 transitions. [2025-03-03 15:58:17,001 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 45 transitions. Word has length 11 [2025-03-03 15:58:17,001 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 15:58:17,001 INFO L471 AbstractCegarLoop]: Abstraction has 37 states and 45 transitions. [2025-03-03 15:58:17,002 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 15:58:17,002 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 45 transitions. [2025-03-03 15:58:17,002 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2025-03-03 15:58:17,002 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 15:58:17,003 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 15:58:17,003 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-03-03 15:58:17,003 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 15:58:17,003 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 15:58:17,003 INFO L85 PathProgramCache]: Analyzing trace with hash -264142809, now seen corresponding path program 1 times [2025-03-03 15:58:17,003 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 15:58:17,003 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1575418239] [2025-03-03 15:58:17,003 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 15:58:17,004 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 15:58:17,016 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 11 statements into 1 equivalence classes. [2025-03-03 15:58:17,022 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 11 of 11 statements. [2025-03-03 15:58:17,022 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 15:58:17,022 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 15:58:17,081 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 15:58:17,081 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 15:58:17,081 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1575418239] [2025-03-03 15:58:17,081 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1575418239] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 15:58:17,081 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 15:58:17,081 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2025-03-03 15:58:17,081 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1835070019] [2025-03-03 15:58:17,081 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 15:58:17,082 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2025-03-03 15:58:17,082 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 15:58:17,083 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2025-03-03 15:58:17,083 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-03-03 15:58:17,083 INFO L87 Difference]: Start difference. First operand 37 states and 45 transitions. Second operand has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 15:58:17,105 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 15:58:17,105 INFO L93 Difference]: Finished difference Result 57 states and 73 transitions. [2025-03-03 15:58:17,106 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2025-03-03 15:58:17,106 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 11 [2025-03-03 15:58:17,106 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 15:58:17,107 INFO L225 Difference]: With dead ends: 57 [2025-03-03 15:58:17,107 INFO L226 Difference]: Without dead ends: 41 [2025-03-03 15:58:17,108 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-03-03 15:58:17,109 INFO L435 NwaCegarLoop]: 35 mSDtfsCounter, 5 mSDsluCounter, 32 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 67 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 15:58:17,109 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 67 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 15:58:17,110 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2025-03-03 15:58:17,113 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 37. [2025-03-03 15:58:17,114 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 25 states have (on average 1.2) internal successors, (30), 27 states have internal predecessors, (30), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-03-03 15:58:17,115 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 43 transitions. [2025-03-03 15:58:17,115 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 43 transitions. Word has length 11 [2025-03-03 15:58:17,115 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 15:58:17,115 INFO L471 AbstractCegarLoop]: Abstraction has 37 states and 43 transitions. [2025-03-03 15:58:17,115 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 15:58:17,115 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 43 transitions. [2025-03-03 15:58:17,116 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2025-03-03 15:58:17,116 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 15:58:17,116 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 15:58:17,116 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-03-03 15:58:17,116 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 15:58:17,117 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 15:58:17,117 INFO L85 PathProgramCache]: Analyzing trace with hash 373208147, now seen corresponding path program 1 times [2025-03-03 15:58:17,117 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 15:58:17,119 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [830431757] [2025-03-03 15:58:17,119 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 15:58:17,119 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 15:58:17,125 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 14 statements into 1 equivalence classes. [2025-03-03 15:58:17,132 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 14 of 14 statements. [2025-03-03 15:58:17,132 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 15:58:17,132 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 15:58:17,223 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 15:58:17,224 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 15:58:17,224 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [830431757] [2025-03-03 15:58:17,224 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [830431757] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 15:58:17,224 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 15:58:17,224 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2025-03-03 15:58:17,224 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1542684747] [2025-03-03 15:58:17,224 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 15:58:17,224 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2025-03-03 15:58:17,224 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 15:58:17,225 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2025-03-03 15:58:17,225 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-03-03 15:58:17,225 INFO L87 Difference]: Start difference. First operand 37 states and 43 transitions. Second operand has 3 states, 3 states have (on average 4.333333333333333) internal successors, (13), 3 states have internal predecessors, (13), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 15:58:17,246 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 15:58:17,246 INFO L93 Difference]: Finished difference Result 51 states and 61 transitions. [2025-03-03 15:58:17,247 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2025-03-03 15:58:17,247 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.333333333333333) internal successors, (13), 3 states have internal predecessors, (13), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 14 [2025-03-03 15:58:17,247 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 15:58:17,248 INFO L225 Difference]: With dead ends: 51 [2025-03-03 15:58:17,248 INFO L226 Difference]: Without dead ends: 39 [2025-03-03 15:58:17,248 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-03-03 15:58:17,249 INFO L435 NwaCegarLoop]: 35 mSDtfsCounter, 0 mSDsluCounter, 31 mSDsCounter, 0 mSdLazyCounter, 10 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 66 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 10 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 15:58:17,249 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 66 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 10 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 15:58:17,250 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2025-03-03 15:58:17,253 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 39. [2025-03-03 15:58:17,253 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 27 states have (on average 1.1851851851851851) internal successors, (32), 29 states have internal predecessors, (32), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-03-03 15:58:17,254 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 45 transitions. [2025-03-03 15:58:17,255 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 45 transitions. Word has length 14 [2025-03-03 15:58:17,255 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 15:58:17,255 INFO L471 AbstractCegarLoop]: Abstraction has 39 states and 45 transitions. [2025-03-03 15:58:17,255 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.333333333333333) internal successors, (13), 3 states have internal predecessors, (13), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 15:58:17,255 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 45 transitions. [2025-03-03 15:58:17,256 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2025-03-03 15:58:17,256 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 15:58:17,256 INFO L218 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 15:58:17,256 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2025-03-03 15:58:17,256 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 15:58:17,257 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 15:58:17,257 INFO L85 PathProgramCache]: Analyzing trace with hash -1424638767, now seen corresponding path program 1 times [2025-03-03 15:58:17,257 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 15:58:17,257 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [689268066] [2025-03-03 15:58:17,257 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 15:58:17,257 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 15:58:17,277 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 16 statements into 1 equivalence classes. [2025-03-03 15:58:17,283 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 16 of 16 statements. [2025-03-03 15:58:17,283 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 15:58:17,283 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 15:58:17,361 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 15:58:17,362 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 15:58:17,362 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [689268066] [2025-03-03 15:58:17,362 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [689268066] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 15:58:17,362 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1087853783] [2025-03-03 15:58:17,362 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 15:58:17,362 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 15:58:17,362 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 15:58:17,364 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) [2025-03-03 15:58:17,366 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-03-03 15:58:17,397 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 16 statements into 1 equivalence classes. [2025-03-03 15:58:17,410 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 16 of 16 statements. [2025-03-03 15:58:17,410 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 15:58:17,410 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 15:58:17,412 INFO L256 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-03 15:58:17,415 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 15:58:17,512 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 15:58:17,512 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 15:58:17,583 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 15:58:17,584 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1087853783] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 15:58:17,584 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 15:58:17,584 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 5, 5] total 10 [2025-03-03 15:58:17,584 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1240682422] [2025-03-03 15:58:17,584 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 15:58:17,584 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-03-03 15:58:17,585 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 15:58:17,586 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-03-03 15:58:17,587 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=60, Unknown=0, NotChecked=0, Total=90 [2025-03-03 15:58:17,587 INFO L87 Difference]: Start difference. First operand 39 states and 45 transitions. Second operand has 10 states, 10 states have (on average 3.3) internal successors, (33), 10 states have internal predecessors, (33), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 15:58:17,630 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 15:58:17,630 INFO L93 Difference]: Finished difference Result 55 states and 66 transitions. [2025-03-03 15:58:17,630 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-03 15:58:17,630 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.3) internal successors, (33), 10 states have internal predecessors, (33), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 16 [2025-03-03 15:58:17,631 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 15:58:17,631 INFO L225 Difference]: With dead ends: 55 [2025-03-03 15:58:17,631 INFO L226 Difference]: Without dead ends: 43 [2025-03-03 15:58:17,632 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=30, Invalid=60, Unknown=0, NotChecked=0, Total=90 [2025-03-03 15:58:17,632 INFO L435 NwaCegarLoop]: 35 mSDtfsCounter, 0 mSDsluCounter, 124 mSDsCounter, 0 mSdLazyCounter, 33 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 159 SdHoareTripleChecker+Invalid, 34 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 33 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 15:58:17,633 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 159 Invalid, 34 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 33 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 15:58:17,634 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2025-03-03 15:58:17,637 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 43. [2025-03-03 15:58:17,637 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 31 states have (on average 1.1612903225806452) internal successors, (36), 33 states have internal predecessors, (36), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-03-03 15:58:17,638 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 49 transitions. [2025-03-03 15:58:17,638 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 49 transitions. Word has length 16 [2025-03-03 15:58:17,638 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 15:58:17,638 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 49 transitions. [2025-03-03 15:58:17,638 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.3) internal successors, (33), 10 states have internal predecessors, (33), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 15:58:17,638 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 49 transitions. [2025-03-03 15:58:17,639 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2025-03-03 15:58:17,639 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 15:58:17,639 INFO L218 NwaCegarLoop]: trace histogram [4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 15:58:17,645 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2025-03-03 15:58:17,840 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 15:58:17,840 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 15:58:17,841 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 15:58:17,841 INFO L85 PathProgramCache]: Analyzing trace with hash 793720653, now seen corresponding path program 2 times [2025-03-03 15:58:17,841 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 15:58:17,841 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [11354175] [2025-03-03 15:58:17,841 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 15:58:17,841 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 15:58:17,846 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 20 statements into 2 equivalence classes. [2025-03-03 15:58:17,862 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 20 of 20 statements. [2025-03-03 15:58:17,862 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 15:58:17,862 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 15:58:17,983 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 6 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 15:58:17,983 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 15:58:17,983 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [11354175] [2025-03-03 15:58:17,983 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [11354175] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 15:58:17,983 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1706905861] [2025-03-03 15:58:17,983 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 15:58:17,983 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 15:58:17,983 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 15:58:17,986 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) [2025-03-03 15:58:17,987 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-03-03 15:58:18,013 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 20 statements into 2 equivalence classes. [2025-03-03 15:58:18,027 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 20 of 20 statements. [2025-03-03 15:58:18,027 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 15:58:18,027 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 15:58:18,028 INFO L256 TraceCheckSpWp]: Trace formula consists of 88 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-03 15:58:18,029 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 15:58:18,143 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 12 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 15:58:18,144 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 15:58:18,222 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 16 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 15:58:18,222 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1706905861] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 15:58:18,222 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 15:58:18,222 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 17 [2025-03-03 15:58:18,222 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1176800867] [2025-03-03 15:58:18,223 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 15:58:18,223 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2025-03-03 15:58:18,223 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 15:58:18,223 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2025-03-03 15:58:18,224 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=97, Invalid=175, Unknown=0, NotChecked=0, Total=272 [2025-03-03 15:58:18,224 INFO L87 Difference]: Start difference. First operand 43 states and 49 transitions. Second operand has 17 states, 17 states have (on average 2.6470588235294117) internal successors, (45), 17 states have internal predecessors, (45), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 15:58:18,335 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 15:58:18,336 INFO L93 Difference]: Finished difference Result 64 states and 81 transitions. [2025-03-03 15:58:18,337 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-03-03 15:58:18,337 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 2.6470588235294117) internal successors, (45), 17 states have internal predecessors, (45), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 20 [2025-03-03 15:58:18,337 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 15:58:18,338 INFO L225 Difference]: With dead ends: 64 [2025-03-03 15:58:18,338 INFO L226 Difference]: Without dead ends: 50 [2025-03-03 15:58:18,338 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 117 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=121, Invalid=221, Unknown=0, NotChecked=0, Total=342 [2025-03-03 15:58:18,339 INFO L435 NwaCegarLoop]: 34 mSDtfsCounter, 7 mSDsluCounter, 248 mSDsCounter, 0 mSdLazyCounter, 113 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 282 SdHoareTripleChecker+Invalid, 120 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 113 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 15:58:18,339 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 282 Invalid, 120 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 113 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 15:58:18,339 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2025-03-03 15:58:18,344 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 48. [2025-03-03 15:58:18,345 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 36 states have (on average 1.1388888888888888) internal successors, (41), 38 states have internal predecessors, (41), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-03-03 15:58:18,345 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 54 transitions. [2025-03-03 15:58:18,346 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 54 transitions. Word has length 20 [2025-03-03 15:58:18,346 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 15:58:18,346 INFO L471 AbstractCegarLoop]: Abstraction has 48 states and 54 transitions. [2025-03-03 15:58:18,346 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 2.6470588235294117) internal successors, (45), 17 states have internal predecessors, (45), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 15:58:18,346 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 54 transitions. [2025-03-03 15:58:18,346 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2025-03-03 15:58:18,346 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 15:58:18,347 INFO L218 NwaCegarLoop]: trace histogram [5, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 15:58:18,353 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2025-03-03 15:58:18,547 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 15:58:18,548 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 15:58:18,548 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 15:58:18,548 INFO L85 PathProgramCache]: Analyzing trace with hash 1448466508, now seen corresponding path program 3 times [2025-03-03 15:58:18,548 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 15:58:18,548 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [53041803] [2025-03-03 15:58:18,548 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-03 15:58:18,549 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 15:58:18,556 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 22 statements into 6 equivalence classes. [2025-03-03 15:58:18,573 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 22 of 22 statements. [2025-03-03 15:58:18,574 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-03-03 15:58:18,574 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 15:58:18,575 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [331042042] [2025-03-03 15:58:18,576 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-03 15:58:18,576 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 15:58:18,576 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 15:58:18,577 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) [2025-03-03 15:58:18,579 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-03-03 15:58:18,606 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 22 statements into 6 equivalence classes. [2025-03-03 15:58:18,618 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) and asserted 18 of 22 statements. [2025-03-03 15:58:18,618 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2025-03-03 15:58:18,618 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 15:58:18,619 INFO L256 TraceCheckSpWp]: Trace formula consists of 84 conjuncts, 24 conjuncts are in the unsatisfiable core [2025-03-03 15:58:18,621 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 15:58:18,725 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-03-03 15:58:18,725 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 15:58:18,983 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-03-03 15:58:18,983 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 15:58:18,983 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [53041803] [2025-03-03 15:58:18,983 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 15:58:18,984 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [331042042] [2025-03-03 15:58:18,984 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [331042042] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 15:58:18,984 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 15:58:18,984 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 16 [2025-03-03 15:58:18,984 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [544900781] [2025-03-03 15:58:18,984 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 15:58:18,984 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-03-03 15:58:18,984 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 15:58:18,984 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-03-03 15:58:18,985 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=37, Invalid=203, Unknown=0, NotChecked=0, Total=240 [2025-03-03 15:58:18,985 INFO L87 Difference]: Start difference. First operand 48 states and 54 transitions. Second operand has 16 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 14 states have internal predecessors, (29), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 15:58:19,308 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 15:58:19,308 INFO L93 Difference]: Finished difference Result 69 states and 83 transitions. [2025-03-03 15:58:19,308 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2025-03-03 15:58:19,308 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 14 states have internal predecessors, (29), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 22 [2025-03-03 15:58:19,308 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 15:58:19,309 INFO L225 Difference]: With dead ends: 69 [2025-03-03 15:58:19,309 INFO L226 Difference]: Without dead ends: 66 [2025-03-03 15:58:19,309 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 27 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=60, Invalid=320, Unknown=0, NotChecked=0, Total=380 [2025-03-03 15:58:19,310 INFO L435 NwaCegarLoop]: 31 mSDtfsCounter, 8 mSDsluCounter, 350 mSDsCounter, 0 mSdLazyCounter, 236 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 381 SdHoareTripleChecker+Invalid, 246 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 236 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 15:58:19,310 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 381 Invalid, 246 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 236 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 15:58:19,310 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 66 states. [2025-03-03 15:58:19,315 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 66 to 63. [2025-03-03 15:58:19,316 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 47 states have (on average 1.2127659574468086) internal successors, (57), 51 states have internal predecessors, (57), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) [2025-03-03 15:58:19,316 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 75 transitions. [2025-03-03 15:58:19,316 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 75 transitions. Word has length 22 [2025-03-03 15:58:19,317 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 15:58:19,317 INFO L471 AbstractCegarLoop]: Abstraction has 63 states and 75 transitions. [2025-03-03 15:58:19,317 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 14 states have internal predecessors, (29), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 15:58:19,317 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 75 transitions. [2025-03-03 15:58:19,317 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2025-03-03 15:58:19,317 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 15:58:19,317 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 15:58:19,323 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2025-03-03 15:58:19,522 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 15:58:19,524 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 15:58:19,525 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 15:58:19,525 INFO L85 PathProgramCache]: Analyzing trace with hash 1155762721, now seen corresponding path program 1 times [2025-03-03 15:58:19,525 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 15:58:19,525 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [193040739] [2025-03-03 15:58:19,525 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 15:58:19,525 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 15:58:19,530 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 25 statements into 1 equivalence classes. [2025-03-03 15:58:19,535 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 25 of 25 statements. [2025-03-03 15:58:19,535 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 15:58:19,535 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-03 15:58:19,536 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-03 15:58:19,537 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 25 statements into 1 equivalence classes. [2025-03-03 15:58:19,539 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 25 of 25 statements. [2025-03-03 15:58:19,539 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 15:58:19,539 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-03 15:58:19,549 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-03 15:58:19,549 INFO L340 BasicCegarLoop]: Counterexample is feasible [2025-03-03 15:58:19,550 INFO L782 garLoopResultBuilder]: Registering result UNSAFE for location ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION (1 of 2 remaining) [2025-03-03 15:58:19,551 INFO L782 garLoopResultBuilder]: Registering result UNKNOWN for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 2 remaining) [2025-03-03 15:58:19,551 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2025-03-03 15:58:19,554 INFO L422 BasicCegarLoop]: Path program histogram: [3, 1, 1, 1, 1] [2025-03-03 15:58:19,569 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2025-03-03 15:58:19,572 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 03.03 03:58:19 BoogieIcfgContainer [2025-03-03 15:58:19,572 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2025-03-03 15:58:19,574 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2025-03-03 15:58:19,574 INFO L270 PluginConnector]: Initializing Witness Printer... [2025-03-03 15:58:19,574 INFO L274 PluginConnector]: Witness Printer initialized [2025-03-03 15:58:19,575 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 03:58:16" (3/4) ... [2025-03-03 15:58:19,576 INFO L149 WitnessPrinter]: No result that supports witness generation found [2025-03-03 15:58:19,577 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2025-03-03 15:58:19,578 INFO L158 Benchmark]: Toolchain (without parser) took 3496.85ms. Allocated memory is still 142.6MB. Free memory was 114.5MB in the beginning and 78.0MB in the end (delta: 36.5MB). Peak memory consumption was 35.8MB. Max. memory is 16.1GB. [2025-03-03 15:58:19,578 INFO L158 Benchmark]: CDTParser took 0.25ms. Allocated memory is still 201.3MB. Free memory is still 125.3MB. There was no memory consumed. Max. memory is 16.1GB. [2025-03-03 15:58:19,578 INFO L158 Benchmark]: CACSL2BoogieTranslator took 200.17ms. Allocated memory is still 142.6MB. Free memory was 114.0MB in the beginning and 102.2MB in the end (delta: 11.8MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-03 15:58:19,578 INFO L158 Benchmark]: Boogie Procedure Inliner took 25.75ms. Allocated memory is still 142.6MB. Free memory was 102.2MB in the beginning and 100.8MB in the end (delta: 1.4MB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-03 15:58:19,578 INFO L158 Benchmark]: Boogie Preprocessor took 28.95ms. Allocated memory is still 142.6MB. Free memory was 100.8MB in the beginning and 99.7MB in the end (delta: 1.2MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-03 15:58:19,579 INFO L158 Benchmark]: IcfgBuilder took 250.27ms. Allocated memory is still 142.6MB. Free memory was 99.2MB in the beginning and 85.1MB in the end (delta: 14.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-03 15:58:19,579 INFO L158 Benchmark]: TraceAbstraction took 2981.87ms. Allocated memory is still 142.6MB. Free memory was 84.6MB in the beginning and 78.0MB in the end (delta: 6.5MB). Peak memory consumption was 10.7MB. Max. memory is 16.1GB. [2025-03-03 15:58:19,579 INFO L158 Benchmark]: Witness Printer took 3.51ms. Allocated memory is still 142.6MB. Free memory was 78.0MB in the beginning and 78.0MB in the end (delta: 24.1kB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-03 15:58:19,580 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.25ms. Allocated memory is still 201.3MB. Free memory is still 125.3MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 200.17ms. Allocated memory is still 142.6MB. Free memory was 114.0MB in the beginning and 102.2MB in the end (delta: 11.8MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 25.75ms. Allocated memory is still 142.6MB. Free memory was 102.2MB in the beginning and 100.8MB in the end (delta: 1.4MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 28.95ms. Allocated memory is still 142.6MB. Free memory was 100.8MB in the beginning and 99.7MB in the end (delta: 1.2MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * IcfgBuilder took 250.27ms. Allocated memory is still 142.6MB. Free memory was 99.2MB in the beginning and 85.1MB in the end (delta: 14.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * TraceAbstraction took 2981.87ms. Allocated memory is still 142.6MB. Free memory was 84.6MB in the beginning and 78.0MB in the end (delta: 6.5MB). Peak memory consumption was 10.7MB. Max. memory is 16.1GB. * Witness Printer took 3.51ms. Allocated memory is still 142.6MB. Free memory was 78.0MB in the beginning and 78.0MB in the end (delta: 24.1kB). There was no memory consumed. Max. memory is 16.1GB. * 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 - UnprovableResult [Line: 109]: Unable to prove that a call to reach_error is unreachable Unable to prove that a call to reach_error is unreachable Reason: overapproximation of someBinaryFLOATComparisonOperation at line 98, overapproximation of someBinaryDOUBLEComparisonOperation at line 108, overapproximation of someBinaryArithmeticFLOAToperation at line 102, overapproximation of someBinaryArithmeticFLOAToperation at line 87, overapproximation of someBinaryArithmeticFLOAToperation at line 100, overapproximation of someBinaryArithmeticFLOAToperation at line 92. Possible FailurePath: [L115] COND FALSE !(__VERIFIER_nondet_int()) [L118] CALL main2() [L97] float IN = __VERIFIER_nondet_float(); [L98] CALL assume_abort_if_not(IN > -0.6f && IN < 0.6f) [L82] COND FALSE !(!cond) [L98] RET assume_abort_if_not(IN > -0.6f && IN < 0.6f) [L100] CALL, EXPR f(IN) VAL [\old(x)=111] [L87] return x - (x*x*x)/6.0f + (x*x*x*x*x)/120.0f + (x*x*x*x*x*x*x)/5040.0f; VAL [\old(x)=111] [L100] RET, EXPR f(IN) VAL [IN=111] [L100] CALL, EXPR fp(IN) VAL [\old(x)=111] [L92] return 1 - (x*x)/2.0f + (x*x*x*x)/24.0f + (x*x*x*x*x*x)/720.0f; VAL [\old(x)=111] [L100] RET, EXPR fp(IN) VAL [IN=111] [L100] float x = IN - f(IN)/fp(IN); [L102] CALL, EXPR f(x) VAL [\old(x)=110] [L87] return x - (x*x*x)/6.0f + (x*x*x*x*x)/120.0f + (x*x*x*x*x*x*x)/5040.0f; VAL [\old(x)=110] [L102] RET, EXPR f(x) VAL [IN=111, x=110] [L102] CALL, EXPR fp(x) VAL [\old(x)=110] [L92] return 1 - (x*x)/2.0f + (x*x*x*x)/24.0f + (x*x*x*x*x*x)/720.0f; VAL [\old(x)=110] [L102] RET, EXPR fp(x) VAL [IN=111, x=110] [L102] x = x - f(x)/fp(x) [L108] COND TRUE !(x < 0.1) VAL [IN=111] [L109] reach_error() VAL [IN=111] - UnprovableResult [Line: 27]: Unable to prove that a call to reach_error is unreachable Unable to prove that a call to reach_error is unreachable Reason: Not analyzed. - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 42 locations, 2 error locations. Started 1 CEGAR loops. OverallTime: 2.9s, OverallIterations: 7, TraceHistogramMax: 5, PathProgramHistogramMax: 3, EmptinessCheckTime: 0.0s, AutomataDifference: 0.6s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 29 SdHoareTripleChecker+Valid, 0.3s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 25 mSDsluCounter, 1039 SdHoareTripleChecker+Invalid, 0.2s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 824 mSDsCounter, 20 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 412 IncrementalHoareTripleChecker+Invalid, 432 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 20 mSolverCounterUnsat, 215 mSDtfsCounter, 412 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 136 GetRequests, 90 SyntacticMatches, 0 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 152 ImplicationChecksByTransitivity, 0.5s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=63occurred in iteration=6, InterpolantAutomatonStates: 40, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 6 MinimizatonAttempts, 9 StatesRemovedByMinimization, 3 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.0s SsaConstructionTime, 0.1s SatisfiabilityAnalysisTime, 1.2s InterpolantComputationTime, 177 NumberOfCodeBlocks, 173 NumberOfCodeBlocksAsserted, 20 NumberOfCheckSat, 177 ConstructedInterpolants, 0 QuantifiedInterpolants, 896 SizeOfPredicates, 9 NumberOfNonLiveVariables, 252 ConjunctsInSsa, 44 ConjunctsInUnsatCore, 11 InterpolantComputations, 3 PerfectInterpolantSequences, 45/111 InterpolantCoveringCapability, 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, ConComCheckerStatistics: No data available RESULT: Ultimate could not prove your program: unable to determine feasibility of some traces [2025-03-03 15:58:19,593 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Using bit-precise analysis Retrying with bit-precise analysis ### Bit-precise run ### Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/combinations/gcd_4+newton_2_3.i -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Bitvector.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash a8b52922fdfe93dd417523e4e63c80c50c6631dbe5ff22aa1a5e25c09a617278 --- Real Ultimate output --- This is Ultimate 0.3.0-?-798a7b3-m [2025-03-03 15:58:21,457 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-03 15:58:21,526 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Bitvector.epf [2025-03-03 15:58:21,530 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-03 15:58:21,531 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-03 15:58:21,555 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-03 15:58:21,555 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-03 15:58:21,555 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-03 15:58:21,556 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-03 15:58:21,556 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-03 15:58:21,556 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-03 15:58:21,556 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-03 15:58:21,556 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-03 15:58:21,556 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-03 15:58:21,556 INFO L153 SettingsManager]: * Use SBE=true [2025-03-03 15:58:21,556 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-03 15:58:21,556 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-03 15:58:21,556 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-03 15:58:21,556 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-03 15:58:21,556 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-03 15:58:21,557 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-03 15:58:21,557 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-03 15:58:21,557 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-03 15:58:21,557 INFO L153 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2025-03-03 15:58:21,557 INFO L153 SettingsManager]: * Use bitvectors instead of ints=true [2025-03-03 15:58:21,557 INFO L153 SettingsManager]: * Memory model=HoenickeLindenmann_4ByteResolution [2025-03-03 15:58:21,557 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-03 15:58:21,557 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-03 15:58:21,557 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-03 15:58:21,557 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-03 15:58:21,557 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-03 15:58:21,557 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-03 15:58:21,557 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-03 15:58:21,557 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-03 15:58:21,557 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 15:58:21,559 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-03 15:58:21,559 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-03 15:58:21,559 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-03 15:58:21,559 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-03 15:58:21,559 INFO L153 SettingsManager]: * Trace refinement strategy=FOX [2025-03-03 15:58:21,559 INFO L153 SettingsManager]: * Command for external solver=cvc4 --incremental --print-success --lang smt [2025-03-03 15:58:21,559 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-03 15:58:21,559 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-03 15:58:21,559 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-03 15:58:21,560 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-03 15:58:21,560 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> a8b52922fdfe93dd417523e4e63c80c50c6631dbe5ff22aa1a5e25c09a617278 [2025-03-03 15:58:21,785 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-03 15:58:21,790 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-03 15:58:21,791 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-03 15:58:21,792 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-03 15:58:21,792 INFO L274 PluginConnector]: CDTParser initialized [2025-03-03 15:58:21,793 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/combinations/gcd_4+newton_2_3.i [2025-03-03 15:58:22,964 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/34d7372fe/32303a3759b740d5a8f4d151f61bf0a4/FLAG389a0f6f8 [2025-03-03 15:58:23,161 INFO L384 CDTParser]: Found 1 translation units. [2025-03-03 15:58:23,162 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/combinations/gcd_4+newton_2_3.i [2025-03-03 15:58:23,170 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/34d7372fe/32303a3759b740d5a8f4d151f61bf0a4/FLAG389a0f6f8 [2025-03-03 15:58:23,537 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/34d7372fe/32303a3759b740d5a8f4d151f61bf0a4 [2025-03-03 15:58:23,539 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-03 15:58:23,540 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-03 15:58:23,541 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-03 15:58:23,541 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-03 15:58:23,545 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-03 15:58:23,546 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 03:58:23" (1/1) ... [2025-03-03 15:58:23,546 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7658afd8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:58:23, skipping insertion in model container [2025-03-03 15:58:23,546 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 03:58:23" (1/1) ... [2025-03-03 15:58:23,558 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-03 15:58:23,654 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/combinations/gcd_4+newton_2_3.i[1224,1237] [2025-03-03 15:58:23,671 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/combinations/gcd_4+newton_2_3.i[2827,2840] [2025-03-03 15:58:23,672 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 15:58:23,681 INFO L200 MainTranslator]: Completed pre-run [2025-03-03 15:58:23,693 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/combinations/gcd_4+newton_2_3.i[1224,1237] [2025-03-03 15:58:23,701 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/combinations/gcd_4+newton_2_3.i[2827,2840] [2025-03-03 15:58:23,702 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 15:58:23,714 INFO L204 MainTranslator]: Completed translation [2025-03-03 15:58:23,715 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:58:23 WrapperNode [2025-03-03 15:58:23,715 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-03 15:58:23,716 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-03 15:58:23,716 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-03 15:58:23,716 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-03 15:58:23,720 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:58:23" (1/1) ... [2025-03-03 15:58:23,733 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:58:23" (1/1) ... [2025-03-03 15:58:23,751 INFO L138 Inliner]: procedures = 28, calls = 26, calls flagged for inlining = 6, calls inlined = 6, statements flattened = 73 [2025-03-03 15:58:23,752 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-03 15:58:23,752 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-03 15:58:23,752 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-03 15:58:23,752 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-03 15:58:23,760 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:58:23" (1/1) ... [2025-03-03 15:58:23,760 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:58:23" (1/1) ... [2025-03-03 15:58:23,762 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:58:23" (1/1) ... [2025-03-03 15:58:23,775 INFO L175 MemorySlicer]: Split 10 memory accesses to 2 slices as follows [2, 8]. 80 percent of accesses are in the largest equivalence class. The 10 initializations are split as follows [2, 8]. The 0 writes are split as follows [0, 0]. [2025-03-03 15:58:23,776 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:58:23" (1/1) ... [2025-03-03 15:58:23,776 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:58:23" (1/1) ... [2025-03-03 15:58:23,786 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:58:23" (1/1) ... [2025-03-03 15:58:23,787 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:58:23" (1/1) ... [2025-03-03 15:58:23,788 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:58:23" (1/1) ... [2025-03-03 15:58:23,788 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:58:23" (1/1) ... [2025-03-03 15:58:23,790 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-03 15:58:23,791 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-03 15:58:23,791 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-03 15:58:23,791 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-03 15:58:23,792 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:58:23" (1/1) ... [2025-03-03 15:58:23,796 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 15:58:23,807 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 15:58:23,825 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2025-03-03 15:58:23,832 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2025-03-03 15:58:23,849 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-03 15:58:23,849 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#0 [2025-03-03 15:58:23,849 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#1 [2025-03-03 15:58:23,849 INFO L130 BoogieDeclarations]: Found specification of procedure fp [2025-03-03 15:58:23,849 INFO L138 BoogieDeclarations]: Found implementation of procedure fp [2025-03-03 15:58:23,849 INFO L130 BoogieDeclarations]: Found specification of procedure f [2025-03-03 15:58:23,849 INFO L138 BoogieDeclarations]: Found implementation of procedure f [2025-03-03 15:58:23,849 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-03 15:58:23,849 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-03 15:58:23,849 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-03-03 15:58:23,849 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-03-03 15:58:23,904 INFO L256 CfgBuilder]: Building ICFG [2025-03-03 15:58:23,905 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-03 15:58:35,976 INFO L? ?]: Removed 22 outVars from TransFormulas that were not future-live. [2025-03-03 15:58:35,977 INFO L307 CfgBuilder]: Performing block encoding [2025-03-03 15:58:35,986 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-03 15:58:35,986 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-03 15:58:35,986 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 03:58:35 BoogieIcfgContainer [2025-03-03 15:58:35,986 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-03 15:58:35,988 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-03 15:58:35,988 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-03 15:58:35,992 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-03 15:58:35,992 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 03.03 03:58:23" (1/3) ... [2025-03-03 15:58:35,993 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@e35591a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 03:58:35, skipping insertion in model container [2025-03-03 15:58:35,993 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:58:23" (2/3) ... [2025-03-03 15:58:35,994 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@e35591a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 03:58:35, skipping insertion in model container [2025-03-03 15:58:35,994 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 03:58:35" (3/3) ... [2025-03-03 15:58:35,995 INFO L128 eAbstractionObserver]: Analyzing ICFG gcd_4+newton_2_3.i [2025-03-03 15:58:36,007 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-03 15:58:36,009 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG gcd_4+newton_2_3.i that has 4 procedures, 42 locations, 1 initial locations, 1 loop locations, and 2 error locations. [2025-03-03 15:58:36,048 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-03 15:58:36,056 INFO L333 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopHeads, 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, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@5304d8a9, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-03 15:58:36,056 INFO L334 AbstractCegarLoop]: Starting to check reachability of 2 error locations. [2025-03-03 15:58:36,059 INFO L276 IsEmpty]: Start isEmpty. Operand has 42 states, 29 states have (on average 1.3793103448275863) internal successors, (40), 31 states have internal predecessors, (40), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2025-03-03 15:58:36,064 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2025-03-03 15:58:36,064 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 15:58:36,064 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 15:58:36,065 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 15:58:36,068 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 15:58:36,069 INFO L85 PathProgramCache]: Analyzing trace with hash -1151646490, now seen corresponding path program 1 times [2025-03-03 15:58:36,075 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-03-03 15:58:36,075 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [150806162] [2025-03-03 15:58:36,076 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 15:58:36,076 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 15:58:36,076 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 15:58:36,078 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) [2025-03-03 15:58:36,079 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-03-03 15:58:36,128 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 11 statements into 1 equivalence classes. [2025-03-03 15:58:36,158 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 11 of 11 statements. [2025-03-03 15:58:36,158 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 15:58:36,158 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 15:58:36,162 INFO L256 TraceCheckSpWp]: Trace formula consists of 42 conjuncts, 4 conjuncts are in the unsatisfiable core [2025-03-03 15:58:36,165 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 15:58:36,262 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 15:58:36,262 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-03 15:58:36,262 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-03-03 15:58:36,262 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [150806162] [2025-03-03 15:58:36,263 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [150806162] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 15:58:36,263 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 15:58:36,263 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2025-03-03 15:58:36,264 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [825334036] [2025-03-03 15:58:36,264 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 15:58:36,267 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2025-03-03 15:58:36,267 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-03-03 15:58:36,280 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2025-03-03 15:58:36,281 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-03-03 15:58:36,283 INFO L87 Difference]: Start difference. First operand has 42 states, 29 states have (on average 1.3793103448275863) internal successors, (40), 31 states have internal predecessors, (40), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 15:58:36,398 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 15:58:36,398 INFO L93 Difference]: Finished difference Result 81 states and 107 transitions. [2025-03-03 15:58:36,399 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2025-03-03 15:58:36,400 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 11 [2025-03-03 15:58:36,400 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 15:58:36,404 INFO L225 Difference]: With dead ends: 81 [2025-03-03 15:58:36,404 INFO L226 Difference]: Without dead ends: 37 [2025-03-03 15:58:36,405 INFO L434 NwaCegarLoop]: 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 [2025-03-03 15:58:36,407 INFO L435 NwaCegarLoop]: 44 mSDtfsCounter, 6 mSDsluCounter, 40 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 84 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 15:58:36,407 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 84 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 15:58:36,417 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2025-03-03 15:58:36,428 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 35. [2025-03-03 15:58:36,428 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 23 states have (on average 1.2173913043478262) internal successors, (28), 25 states have internal predecessors, (28), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-03-03 15:58:36,431 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 41 transitions. [2025-03-03 15:58:36,433 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 41 transitions. Word has length 11 [2025-03-03 15:58:36,433 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 15:58:36,433 INFO L471 AbstractCegarLoop]: Abstraction has 35 states and 41 transitions. [2025-03-03 15:58:36,433 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 15:58:36,433 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 41 transitions. [2025-03-03 15:58:36,434 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2025-03-03 15:58:36,434 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 15:58:36,434 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 15:58:36,447 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2025-03-03 15:58:36,635 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 15:58:36,635 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 15:58:36,636 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 15:58:36,636 INFO L85 PathProgramCache]: Analyzing trace with hash 2048670773, now seen corresponding path program 1 times [2025-03-03 15:58:36,636 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-03-03 15:58:36,636 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [918381984] [2025-03-03 15:58:36,636 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 15:58:36,636 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 15:58:36,636 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 15:58:36,638 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) [2025-03-03 15:58:36,639 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-03-03 15:58:36,667 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 12 statements into 1 equivalence classes. [2025-03-03 15:58:36,683 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 12 of 12 statements. [2025-03-03 15:58:36,683 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 15:58:36,683 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 15:58:36,685 INFO L256 TraceCheckSpWp]: Trace formula consists of 42 conjuncts, 4 conjuncts are in the unsatisfiable core [2025-03-03 15:58:36,687 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 15:58:36,773 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 15:58:36,774 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-03 15:58:36,774 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-03-03 15:58:36,774 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [918381984] [2025-03-03 15:58:36,774 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [918381984] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 15:58:36,774 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 15:58:36,774 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2025-03-03 15:58:36,774 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [884832813] [2025-03-03 15:58:36,774 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 15:58:36,777 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2025-03-03 15:58:36,777 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-03-03 15:58:36,778 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2025-03-03 15:58:36,778 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-03-03 15:58:36,778 INFO L87 Difference]: Start difference. First operand 35 states and 41 transitions. Second operand has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 3 states have internal predecessors, (11), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 15:58:36,893 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 15:58:36,893 INFO L93 Difference]: Finished difference Result 50 states and 61 transitions. [2025-03-03 15:58:36,895 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2025-03-03 15:58:36,895 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 3 states have internal predecessors, (11), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 12 [2025-03-03 15:58:36,895 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 15:58:36,895 INFO L225 Difference]: With dead ends: 50 [2025-03-03 15:58:36,895 INFO L226 Difference]: Without dead ends: 37 [2025-03-03 15:58:36,895 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 10 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-03-03 15:58:36,896 INFO L435 NwaCegarLoop]: 36 mSDtfsCounter, 4 mSDsluCounter, 31 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 67 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 15:58:36,896 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 67 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 15:58:36,897 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2025-03-03 15:58:36,901 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 37. [2025-03-03 15:58:36,901 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 25 states have (on average 1.2) internal successors, (30), 27 states have internal predecessors, (30), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-03-03 15:58:36,902 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 43 transitions. [2025-03-03 15:58:36,902 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 43 transitions. Word has length 12 [2025-03-03 15:58:36,902 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 15:58:36,902 INFO L471 AbstractCegarLoop]: Abstraction has 37 states and 43 transitions. [2025-03-03 15:58:36,902 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 3 states have internal predecessors, (11), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 15:58:36,902 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 43 transitions. [2025-03-03 15:58:36,903 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2025-03-03 15:58:36,903 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 15:58:36,903 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 15:58:36,910 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2025-03-03 15:58:37,103 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 15:58:37,103 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 15:58:37,104 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 15:58:37,104 INFO L85 PathProgramCache]: Analyzing trace with hash 373208147, now seen corresponding path program 1 times [2025-03-03 15:58:37,104 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-03-03 15:58:37,104 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [622176624] [2025-03-03 15:58:37,104 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 15:58:37,104 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 15:58:37,104 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 15:58:37,109 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) [2025-03-03 15:58:37,110 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-03-03 15:58:37,135 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 14 statements into 1 equivalence classes. [2025-03-03 15:58:37,151 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 14 of 14 statements. [2025-03-03 15:58:37,152 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 15:58:37,152 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 15:58:37,156 INFO L256 TraceCheckSpWp]: Trace formula consists of 44 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-03 15:58:37,159 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 15:58:37,589 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 15:58:37,590 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 15:58:37,870 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 15:58:37,871 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-03-03 15:58:37,871 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [622176624] [2025-03-03 15:58:37,871 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [622176624] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 15:58:37,871 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 15:58:37,871 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 6 [2025-03-03 15:58:37,871 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1610080664] [2025-03-03 15:58:37,871 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 15:58:37,871 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-03-03 15:58:37,871 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-03-03 15:58:37,872 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-03 15:58:37,872 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2025-03-03 15:58:37,872 INFO L87 Difference]: Start difference. First operand 37 states and 43 transitions. Second operand has 6 states, 6 states have (on average 3.3333333333333335) internal successors, (20), 6 states have internal predecessors, (20), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 15:58:38,266 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 15:58:38,266 INFO L93 Difference]: Finished difference Result 54 states and 66 transitions. [2025-03-03 15:58:38,267 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-03 15:58:38,267 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 3.3333333333333335) internal successors, (20), 6 states have internal predecessors, (20), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 14 [2025-03-03 15:58:38,267 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 15:58:38,268 INFO L225 Difference]: With dead ends: 54 [2025-03-03 15:58:38,268 INFO L226 Difference]: Without dead ends: 42 [2025-03-03 15:58:38,268 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 27 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2025-03-03 15:58:38,269 INFO L435 NwaCegarLoop]: 34 mSDtfsCounter, 5 mSDsluCounter, 93 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 127 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-03-03 15:58:38,269 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 127 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-03-03 15:58:38,269 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2025-03-03 15:58:38,272 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 40. [2025-03-03 15:58:38,273 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 40 states, 28 states have (on average 1.1785714285714286) internal successors, (33), 30 states have internal predecessors, (33), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-03-03 15:58:38,273 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 46 transitions. [2025-03-03 15:58:38,273 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 46 transitions. Word has length 14 [2025-03-03 15:58:38,273 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 15:58:38,274 INFO L471 AbstractCegarLoop]: Abstraction has 40 states and 46 transitions. [2025-03-03 15:58:38,274 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 3.3333333333333335) internal successors, (20), 6 states have internal predecessors, (20), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 15:58:38,274 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 46 transitions. [2025-03-03 15:58:38,274 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2025-03-03 15:58:38,274 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 15:58:38,274 INFO L218 NwaCegarLoop]: trace histogram [3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 15:58:38,281 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2025-03-03 15:58:38,475 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 15:58:38,475 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 15:58:38,475 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 15:58:38,475 INFO L85 PathProgramCache]: Analyzing trace with hash 1716297167, now seen corresponding path program 1 times [2025-03-03 15:58:38,476 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-03-03 15:58:38,476 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [863434916] [2025-03-03 15:58:38,476 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 15:58:38,476 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 15:58:38,476 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 15:58:38,478 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) [2025-03-03 15:58:38,479 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2025-03-03 15:58:38,503 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 18 statements into 1 equivalence classes. [2025-03-03 15:58:38,520 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 18 of 18 statements. [2025-03-03 15:58:38,520 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 15:58:38,520 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 15:58:38,524 INFO L256 TraceCheckSpWp]: Trace formula consists of 50 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-03-03 15:58:38,526 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 15:58:39,284 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 15:58:39,284 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 15:58:39,970 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 15:58:39,970 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-03-03 15:58:39,970 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [863434916] [2025-03-03 15:58:39,970 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [863434916] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 15:58:39,970 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 15:58:39,970 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2025-03-03 15:58:39,971 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1539282111] [2025-03-03 15:58:39,971 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 15:58:39,971 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-03-03 15:58:39,971 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-03-03 15:58:39,971 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-03-03 15:58:39,972 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=60, Unknown=0, NotChecked=0, Total=90 [2025-03-03 15:58:39,972 INFO L87 Difference]: Start difference. First operand 40 states and 46 transitions. Second operand has 10 states, 10 states have (on average 2.8) internal successors, (28), 10 states have internal predecessors, (28), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 15:58:41,080 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 15:58:41,080 INFO L93 Difference]: Finished difference Result 62 states and 76 transitions. [2025-03-03 15:58:41,081 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-03 15:58:41,081 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.8) internal successors, (28), 10 states have internal predecessors, (28), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 18 [2025-03-03 15:58:41,081 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 15:58:41,081 INFO L225 Difference]: With dead ends: 62 [2025-03-03 15:58:41,081 INFO L226 Difference]: Without dead ends: 49 [2025-03-03 15:58:41,082 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 37 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=57, Invalid=99, Unknown=0, NotChecked=0, Total=156 [2025-03-03 15:58:41,082 INFO L435 NwaCegarLoop]: 34 mSDtfsCounter, 7 mSDsluCounter, 155 mSDsCounter, 0 mSdLazyCounter, 65 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 189 SdHoareTripleChecker+Invalid, 69 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 65 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2025-03-03 15:58:41,082 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 189 Invalid, 69 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 65 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2025-03-03 15:58:41,083 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2025-03-03 15:58:41,087 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 48. [2025-03-03 15:58:41,087 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 36 states have (on average 1.1944444444444444) internal successors, (43), 38 states have internal predecessors, (43), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-03-03 15:58:41,088 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 56 transitions. [2025-03-03 15:58:41,088 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 56 transitions. Word has length 18 [2025-03-03 15:58:41,088 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 15:58:41,088 INFO L471 AbstractCegarLoop]: Abstraction has 48 states and 56 transitions. [2025-03-03 15:58:41,088 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.8) internal successors, (28), 10 states have internal predecessors, (28), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 15:58:41,088 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 56 transitions. [2025-03-03 15:58:41,089 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2025-03-03 15:58:41,089 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 15:58:41,089 INFO L218 NwaCegarLoop]: trace histogram [5, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 15:58:41,096 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2025-03-03 15:58:41,289 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 15:58:41,289 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 15:58:41,290 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 15:58:41,290 INFO L85 PathProgramCache]: Analyzing trace with hash 1448466508, now seen corresponding path program 2 times [2025-03-03 15:58:41,290 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-03-03 15:58:41,290 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1695900062] [2025-03-03 15:58:41,290 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 15:58:41,290 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 15:58:41,290 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 15:58:41,293 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) [2025-03-03 15:58:41,293 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2025-03-03 15:58:41,315 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 22 statements into 2 equivalence classes. [2025-03-03 15:58:41,337 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 22 of 22 statements. [2025-03-03 15:58:41,338 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 15:58:41,338 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 15:58:41,341 INFO L256 TraceCheckSpWp]: Trace formula consists of 56 conjuncts, 18 conjuncts are in the unsatisfiable core [2025-03-03 15:58:41,349 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 15:58:43,303 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-03 15:58:43,303 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 15:58:53,934 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-03 15:58:53,935 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-03-03 15:58:53,935 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1695900062] [2025-03-03 15:58:53,935 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1695900062] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 15:58:53,935 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 15:58:53,935 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 12] total 20 [2025-03-03 15:58:53,935 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [768703024] [2025-03-03 15:58:53,935 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 15:58:53,936 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2025-03-03 15:58:53,936 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-03-03 15:58:53,936 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2025-03-03 15:58:53,936 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=322, Unknown=0, NotChecked=0, Total=380 [2025-03-03 15:58:53,937 INFO L87 Difference]: Start difference. First operand 48 states and 56 transitions. Second operand has 20 states, 18 states have (on average 1.9444444444444444) internal successors, (35), 18 states have internal predecessors, (35), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 15:59:08,333 WARN L286 SmtUtils]: Spent 9.33s on a formula simplification that was a NOOP. DAG size: 30 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2025-03-03 15:59:12,841 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.05s for a HTC check with result UNKNOWN. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2025-03-03 15:59:16,849 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2025-03-03 15:59:20,857 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2025-03-03 15:59:38,807 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2025-03-03 15:59:43,030 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 3.92s for a HTC check with result INVALID. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2025-03-03 15:59:49,078 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 15:59:49,078 INFO L93 Difference]: Finished difference Result 70 states and 86 transitions. [2025-03-03 15:59:49,082 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2025-03-03 15:59:49,082 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 18 states have (on average 1.9444444444444444) internal successors, (35), 18 states have internal predecessors, (35), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 22 [2025-03-03 15:59:49,083 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 15:59:49,083 INFO L225 Difference]: With dead ends: 70 [2025-03-03 15:59:49,083 INFO L226 Difference]: Without dead ends: 67 [2025-03-03 15:59:49,084 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 24 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 45 ImplicationChecksByTransitivity, 38.3s TimeCoverageRelationStatistics Valid=96, Invalid=503, Unknown=1, NotChecked=0, Total=600 [2025-03-03 15:59:49,085 INFO L435 NwaCegarLoop]: 31 mSDtfsCounter, 6 mSDsluCounter, 408 mSDsCounter, 0 mSdLazyCounter, 246 mSolverCounterSat, 9 mSolverCounterUnsat, 4 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 25.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 439 SdHoareTripleChecker+Invalid, 259 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 246 IncrementalHoareTripleChecker+Invalid, 4 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 26.1s IncrementalHoareTripleChecker+Time [2025-03-03 15:59:49,085 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 439 Invalid, 259 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 246 Invalid, 4 Unknown, 0 Unchecked, 26.1s Time] [2025-03-03 15:59:49,086 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2025-03-03 15:59:49,093 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 65. [2025-03-03 15:59:49,093 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 65 states, 49 states have (on average 1.2448979591836735) internal successors, (61), 53 states have internal predecessors, (61), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) [2025-03-03 15:59:49,094 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 65 states to 65 states and 79 transitions. [2025-03-03 15:59:49,094 INFO L78 Accepts]: Start accepts. Automaton has 65 states and 79 transitions. Word has length 22 [2025-03-03 15:59:49,094 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 15:59:49,094 INFO L471 AbstractCegarLoop]: Abstraction has 65 states and 79 transitions. [2025-03-03 15:59:49,094 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 18 states have (on average 1.9444444444444444) internal successors, (35), 18 states have internal predecessors, (35), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 15:59:49,094 INFO L276 IsEmpty]: Start isEmpty. Operand 65 states and 79 transitions. [2025-03-03 15:59:49,095 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2025-03-03 15:59:49,095 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 15:59:49,095 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 15:59:49,103 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2025-03-03 15:59:49,295 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 15:59:49,296 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 15:59:49,296 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 15:59:49,296 INFO L85 PathProgramCache]: Analyzing trace with hash 1155762721, now seen corresponding path program 1 times [2025-03-03 15:59:49,297 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-03-03 15:59:49,297 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [40881916] [2025-03-03 15:59:49,297 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 15:59:49,297 INFO L173 SolverBuilder]: Constructing external solver with command: mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 [2025-03-03 15:59:49,297 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2025-03-03 15:59:49,298 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2025-03-03 15:59:49,299 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (7)] Waiting until timeout for monitored process [2025-03-03 15:59:49,317 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 25 statements into 1 equivalence classes.