./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/combinations/gcd_4+newton_2_8.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_8.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 131b2ae9424ecd75292a5889f04853eea3cca0c3e4c679243c4666d6f4003ffe --- Real Ultimate output --- This is Ultimate 0.3.0-?-798a7b3-m [2025-03-03 15:58:58,717 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-03 15:58:58,776 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:58,782 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-03 15:58:58,783 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-03 15:58:58,803 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-03 15:58:58,804 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-03 15:58:58,805 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-03 15:58:58,805 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-03 15:58:58,805 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-03 15:58:58,806 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-03 15:58:58,806 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-03 15:58:58,806 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-03 15:58:58,806 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-03 15:58:58,806 INFO L153 SettingsManager]: * Use SBE=true [2025-03-03 15:58:58,806 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-03 15:58:58,806 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-03 15:58:58,806 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-03 15:58:58,806 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-03 15:58:58,806 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-03 15:58:58,806 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-03 15:58:58,806 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-03 15:58:58,807 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-03 15:58:58,807 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-03 15:58:58,807 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-03 15:58:58,807 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-03 15:58:58,807 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-03 15:58:58,807 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-03 15:58:58,807 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-03 15:58:58,807 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-03 15:58:58,807 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-03 15:58:58,807 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-03 15:58:58,807 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 15:58:58,807 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-03 15:58:58,807 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-03 15:58:58,807 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-03 15:58:58,807 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-03 15:58:58,807 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-03 15:58:58,807 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-03 15:58:58,807 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-03 15:58:58,807 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-03 15:58:58,807 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-03 15:58:58,808 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-03 15:58:58,808 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 -> 131b2ae9424ecd75292a5889f04853eea3cca0c3e4c679243c4666d6f4003ffe [2025-03-03 15:58:59,048 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-03 15:58:59,056 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-03 15:58:59,058 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-03 15:58:59,059 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-03 15:58:59,059 INFO L274 PluginConnector]: CDTParser initialized [2025-03-03 15:58:59,061 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/combinations/gcd_4+newton_2_8.i [2025-03-03 15:59:00,261 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a77748faa/f963b356c9114167ae93ca586c1faf3e/FLAG4ebb80f05 [2025-03-03 15:59:00,454 INFO L384 CDTParser]: Found 1 translation units. [2025-03-03 15:59:00,455 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/combinations/gcd_4+newton_2_8.i [2025-03-03 15:59:00,467 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a77748faa/f963b356c9114167ae93ca586c1faf3e/FLAG4ebb80f05 [2025-03-03 15:59:00,835 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a77748faa/f963b356c9114167ae93ca586c1faf3e [2025-03-03 15:59:00,837 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-03 15:59:00,838 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-03 15:59:00,839 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-03 15:59:00,840 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-03 15:59:00,842 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-03 15:59:00,843 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 03:59:00" (1/1) ... [2025-03-03 15:59:00,843 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7e6ca0d7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:59:00, skipping insertion in model container [2025-03-03 15:59:00,844 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 03:59:00" (1/1) ... [2025-03-03 15:59:00,856 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-03 15:59:00,952 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_8.i[1224,1237] [2025-03-03 15:59:00,967 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_8.i[2827,2840] [2025-03-03 15:59:00,968 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 15:59:00,974 INFO L200 MainTranslator]: Completed pre-run [2025-03-03 15:59:00,981 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_8.i[1224,1237] [2025-03-03 15:59:00,987 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_8.i[2827,2840] [2025-03-03 15:59:00,988 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 15:59:00,998 INFO L204 MainTranslator]: Completed translation [2025-03-03 15:59:00,999 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:59:00 WrapperNode [2025-03-03 15:59:00,999 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-03 15:59:01,000 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-03 15:59:01,000 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-03 15:59:01,000 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-03 15:59:01,004 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:59:00" (1/1) ... [2025-03-03 15:59:01,009 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:59:00" (1/1) ... [2025-03-03 15:59:01,026 INFO L138 Inliner]: procedures = 27, calls = 26, calls flagged for inlining = 6, calls inlined = 6, statements flattened = 76 [2025-03-03 15:59:01,027 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-03 15:59:01,027 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-03 15:59:01,027 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-03 15:59:01,027 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-03 15:59:01,035 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:59:00" (1/1) ... [2025-03-03 15:59:01,036 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:59:00" (1/1) ... [2025-03-03 15:59:01,037 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:59:00" (1/1) ... [2025-03-03 15:59:01,050 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:59:01,055 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:59:00" (1/1) ... [2025-03-03 15:59:01,055 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:59:00" (1/1) ... [2025-03-03 15:59:01,062 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:59:00" (1/1) ... [2025-03-03 15:59:01,062 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:59:00" (1/1) ... [2025-03-03 15:59:01,063 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:59:00" (1/1) ... [2025-03-03 15:59:01,063 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:59:00" (1/1) ... [2025-03-03 15:59:01,064 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-03 15:59:01,065 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-03 15:59:01,065 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-03 15:59:01,065 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-03 15:59:01,066 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:59:00" (1/1) ... [2025-03-03 15:59:01,071 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 15:59:01,081 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 15:59:01,092 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:59:01,097 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:59:01,111 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-03 15:59:01,111 INFO L130 BoogieDeclarations]: Found specification of procedure fp [2025-03-03 15:59:01,111 INFO L138 BoogieDeclarations]: Found implementation of procedure fp [2025-03-03 15:59:01,111 INFO L130 BoogieDeclarations]: Found specification of procedure f [2025-03-03 15:59:01,111 INFO L138 BoogieDeclarations]: Found implementation of procedure f [2025-03-03 15:59:01,111 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-03 15:59:01,111 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2025-03-03 15:59:01,111 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-03 15:59:01,111 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-03 15:59:01,111 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-03-03 15:59:01,111 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-03-03 15:59:01,156 INFO L256 CfgBuilder]: Building ICFG [2025-03-03 15:59:01,157 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-03 15:59:01,285 INFO L? ?]: Removed 23 outVars from TransFormulas that were not future-live. [2025-03-03 15:59:01,285 INFO L307 CfgBuilder]: Performing block encoding [2025-03-03 15:59:01,295 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-03 15:59:01,297 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-03 15:59:01,297 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 03:59:01 BoogieIcfgContainer [2025-03-03 15:59:01,298 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-03 15:59:01,299 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-03 15:59:01,300 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-03 15:59:01,303 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-03 15:59:01,303 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 03.03 03:59:00" (1/3) ... [2025-03-03 15:59:01,304 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@54335018 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 03:59:01, skipping insertion in model container [2025-03-03 15:59:01,304 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:59:00" (2/3) ... [2025-03-03 15:59:01,304 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@54335018 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 03:59:01, skipping insertion in model container [2025-03-03 15:59:01,304 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 03:59:01" (3/3) ... [2025-03-03 15:59:01,305 INFO L128 eAbstractionObserver]: Analyzing ICFG gcd_4+newton_2_8.i [2025-03-03 15:59:01,316 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-03 15:59:01,317 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG gcd_4+newton_2_8.i that has 4 procedures, 42 locations, 1 initial locations, 1 loop locations, and 2 error locations. [2025-03-03 15:59:01,359 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-03 15:59:01,366 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;@2cf9b646, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-03 15:59:01,366 INFO L334 AbstractCegarLoop]: Starting to check reachability of 2 error locations. [2025-03-03 15:59:01,370 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:59:01,375 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2025-03-03 15:59:01,375 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 15:59:01,375 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 15:59:01,376 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 15:59:01,380 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 15:59:01,381 INFO L85 PathProgramCache]: Analyzing trace with hash -1151646490, now seen corresponding path program 1 times [2025-03-03 15:59:01,386 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 15:59:01,386 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1978422154] [2025-03-03 15:59:01,388 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 15:59:01,388 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 15:59:01,447 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 11 statements into 1 equivalence classes. [2025-03-03 15:59:01,466 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 11 of 11 statements. [2025-03-03 15:59:01,467 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 15:59:01,467 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 15:59:01,608 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:59:01,610 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 15:59:01,610 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1978422154] [2025-03-03 15:59:01,611 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1978422154] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 15:59:01,611 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 15:59:01,611 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2025-03-03 15:59:01,612 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [400659349] [2025-03-03 15:59:01,616 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 15:59:01,618 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2025-03-03 15:59:01,618 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 15:59:01,630 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2025-03-03 15:59:01,631 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-03-03 15:59:01,632 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:59:01,675 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 15:59:01,675 INFO L93 Difference]: Finished difference Result 80 states and 105 transitions. [2025-03-03 15:59:01,677 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2025-03-03 15:59:01,678 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:59:01,679 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 15:59:01,683 INFO L225 Difference]: With dead ends: 80 [2025-03-03 15:59:01,683 INFO L226 Difference]: Without dead ends: 37 [2025-03-03 15:59:01,685 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:59:01,686 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:59:01,687 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:59:01,695 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2025-03-03 15:59:01,707 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 37. [2025-03-03 15:59:01,708 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:59:01,712 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 45 transitions. [2025-03-03 15:59:01,713 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 45 transitions. Word has length 11 [2025-03-03 15:59:01,715 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 15:59:01,715 INFO L471 AbstractCegarLoop]: Abstraction has 37 states and 45 transitions. [2025-03-03 15:59:01,715 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:59:01,715 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 45 transitions. [2025-03-03 15:59:01,716 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2025-03-03 15:59:01,717 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 15:59:01,717 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 15:59:01,717 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-03-03 15:59:01,718 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 15:59:01,718 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 15:59:01,718 INFO L85 PathProgramCache]: Analyzing trace with hash -264142809, now seen corresponding path program 1 times [2025-03-03 15:59:01,718 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 15:59:01,719 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1228436532] [2025-03-03 15:59:01,719 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 15:59:01,719 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 15:59:01,726 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 11 statements into 1 equivalence classes. [2025-03-03 15:59:01,730 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 11 of 11 statements. [2025-03-03 15:59:01,731 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 15:59:01,731 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 15:59:01,797 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:59:01,797 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 15:59:01,797 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1228436532] [2025-03-03 15:59:01,797 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1228436532] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 15:59:01,798 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 15:59:01,798 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2025-03-03 15:59:01,798 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1572063472] [2025-03-03 15:59:01,798 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 15:59:01,799 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2025-03-03 15:59:01,799 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 15:59:01,800 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2025-03-03 15:59:01,800 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-03-03 15:59:01,801 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:59:01,824 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 15:59:01,824 INFO L93 Difference]: Finished difference Result 57 states and 73 transitions. [2025-03-03 15:59:01,829 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2025-03-03 15:59:01,829 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:59:01,829 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 15:59:01,831 INFO L225 Difference]: With dead ends: 57 [2025-03-03 15:59:01,832 INFO L226 Difference]: Without dead ends: 41 [2025-03-03 15:59:01,832 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:59:01,833 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:59:01,833 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:59:01,834 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2025-03-03 15:59:01,839 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 37. [2025-03-03 15:59:01,840 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:59:01,841 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 43 transitions. [2025-03-03 15:59:01,842 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 43 transitions. Word has length 11 [2025-03-03 15:59:01,842 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 15:59:01,842 INFO L471 AbstractCegarLoop]: Abstraction has 37 states and 43 transitions. [2025-03-03 15:59:01,843 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:59:01,843 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 43 transitions. [2025-03-03 15:59:01,843 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2025-03-03 15:59:01,844 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 15:59:01,844 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 15:59:01,844 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-03-03 15:59:01,844 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 15:59:01,844 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 15:59:01,846 INFO L85 PathProgramCache]: Analyzing trace with hash 373208147, now seen corresponding path program 1 times [2025-03-03 15:59:01,846 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 15:59:01,846 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [444648643] [2025-03-03 15:59:01,846 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 15:59:01,846 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 15:59:01,853 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 14 statements into 1 equivalence classes. [2025-03-03 15:59:01,863 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 14 of 14 statements. [2025-03-03 15:59:01,863 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 15:59:01,863 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 15:59:01,968 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:59:01,969 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 15:59:01,969 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [444648643] [2025-03-03 15:59:01,969 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [444648643] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 15:59:01,970 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 15:59:01,970 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2025-03-03 15:59:01,970 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [790338977] [2025-03-03 15:59:01,970 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 15:59:01,970 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2025-03-03 15:59:01,971 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 15:59:01,971 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2025-03-03 15:59:01,971 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-03-03 15:59:01,971 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:59:01,993 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 15:59:01,993 INFO L93 Difference]: Finished difference Result 51 states and 61 transitions. [2025-03-03 15:59:01,995 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2025-03-03 15:59:01,995 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:59:01,996 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 15:59:01,996 INFO L225 Difference]: With dead ends: 51 [2025-03-03 15:59:01,997 INFO L226 Difference]: Without dead ends: 39 [2025-03-03 15:59:01,997 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:59:01,998 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:59:01,998 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:59:01,999 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2025-03-03 15:59:02,013 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 39. [2025-03-03 15:59:02,014 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:59:02,014 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 45 transitions. [2025-03-03 15:59:02,014 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 45 transitions. Word has length 14 [2025-03-03 15:59:02,015 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 15:59:02,015 INFO L471 AbstractCegarLoop]: Abstraction has 39 states and 45 transitions. [2025-03-03 15:59:02,015 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:59:02,015 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 45 transitions. [2025-03-03 15:59:02,015 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2025-03-03 15:59:02,015 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 15:59:02,015 INFO L218 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 15:59:02,017 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2025-03-03 15:59:02,018 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 15:59:02,018 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 15:59:02,018 INFO L85 PathProgramCache]: Analyzing trace with hash -1424638767, now seen corresponding path program 1 times [2025-03-03 15:59:02,018 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 15:59:02,018 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1618498714] [2025-03-03 15:59:02,018 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 15:59:02,018 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 15:59:02,023 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 16 statements into 1 equivalence classes. [2025-03-03 15:59:02,029 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 16 of 16 statements. [2025-03-03 15:59:02,029 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 15:59:02,029 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 15:59:02,129 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:59:02,130 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 15:59:02,130 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1618498714] [2025-03-03 15:59:02,130 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1618498714] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 15:59:02,130 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1131876876] [2025-03-03 15:59:02,130 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 15:59:02,130 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 15:59:02,130 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 15:59:02,132 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:59:02,134 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:59:02,161 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 16 statements into 1 equivalence classes. [2025-03-03 15:59:02,177 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 16 of 16 statements. [2025-03-03 15:59:02,177 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 15:59:02,177 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 15:59:02,180 INFO L256 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-03 15:59:02,183 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 15:59:02,263 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:59:02,263 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 15:59:02,327 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:59:02,327 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1131876876] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 15:59:02,327 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 15:59:02,327 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 5, 5] total 10 [2025-03-03 15:59:02,328 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1365378085] [2025-03-03 15:59:02,328 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 15:59:02,328 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-03-03 15:59:02,328 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 15:59:02,328 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-03-03 15:59:02,328 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=60, Unknown=0, NotChecked=0, Total=90 [2025-03-03 15:59:02,329 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:59:02,374 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 15:59:02,374 INFO L93 Difference]: Finished difference Result 55 states and 66 transitions. [2025-03-03 15:59:02,374 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-03 15:59:02,374 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:59:02,375 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 15:59:02,375 INFO L225 Difference]: With dead ends: 55 [2025-03-03 15:59:02,375 INFO L226 Difference]: Without dead ends: 43 [2025-03-03 15:59:02,375 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:59:02,376 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:59:02,376 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:59:02,376 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2025-03-03 15:59:02,380 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 43. [2025-03-03 15:59:02,380 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:59:02,380 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 49 transitions. [2025-03-03 15:59:02,381 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 49 transitions. Word has length 16 [2025-03-03 15:59:02,381 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 15:59:02,381 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 49 transitions. [2025-03-03 15:59:02,381 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:59:02,381 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 49 transitions. [2025-03-03 15:59:02,381 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2025-03-03 15:59:02,383 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 15:59:02,383 INFO L218 NwaCegarLoop]: trace histogram [4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 15:59:02,390 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2025-03-03 15:59:02,583 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:59:02,584 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 15:59:02,584 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 15:59:02,584 INFO L85 PathProgramCache]: Analyzing trace with hash 793720653, now seen corresponding path program 2 times [2025-03-03 15:59:02,584 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 15:59:02,584 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [530797660] [2025-03-03 15:59:02,584 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 15:59:02,584 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 15:59:02,590 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 20 statements into 2 equivalence classes. [2025-03-03 15:59:02,603 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 20 of 20 statements. [2025-03-03 15:59:02,603 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 15:59:02,603 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 15:59:02,727 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:59:02,727 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 15:59:02,727 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [530797660] [2025-03-03 15:59:02,727 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [530797660] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 15:59:02,727 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1164473825] [2025-03-03 15:59:02,727 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 15:59:02,727 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 15:59:02,727 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 15:59:02,729 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:59:02,731 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:59:02,761 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 20 statements into 2 equivalence classes. [2025-03-03 15:59:02,776 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 20 of 20 statements. [2025-03-03 15:59:02,776 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 15:59:02,777 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 15:59:02,778 INFO L256 TraceCheckSpWp]: Trace formula consists of 88 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-03 15:59:02,779 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 15:59:02,904 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:59:02,907 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 15:59:02,978 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:59:02,980 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1164473825] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 15:59:02,980 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 15:59:02,982 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 17 [2025-03-03 15:59:02,982 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [126541965] [2025-03-03 15:59:02,982 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 15:59:02,982 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2025-03-03 15:59:02,982 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 15:59:02,983 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2025-03-03 15:59:02,983 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=97, Invalid=175, Unknown=0, NotChecked=0, Total=272 [2025-03-03 15:59:02,983 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:59:03,094 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 15:59:03,094 INFO L93 Difference]: Finished difference Result 64 states and 81 transitions. [2025-03-03 15:59:03,094 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-03-03 15:59:03,094 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:59:03,095 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 15:59:03,095 INFO L225 Difference]: With dead ends: 64 [2025-03-03 15:59:03,095 INFO L226 Difference]: Without dead ends: 50 [2025-03-03 15:59:03,095 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:59:03,096 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:59:03,096 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:59:03,096 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2025-03-03 15:59:03,099 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 48. [2025-03-03 15:59:03,100 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:59:03,100 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 54 transitions. [2025-03-03 15:59:03,101 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 54 transitions. Word has length 20 [2025-03-03 15:59:03,101 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 15:59:03,101 INFO L471 AbstractCegarLoop]: Abstraction has 48 states and 54 transitions. [2025-03-03 15:59:03,101 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:59:03,101 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 54 transitions. [2025-03-03 15:59:03,101 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2025-03-03 15:59:03,102 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 15:59:03,102 INFO L218 NwaCegarLoop]: trace histogram [5, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 15:59:03,109 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:59:03,302 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:59:03,303 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 15:59:03,303 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 15:59:03,304 INFO L85 PathProgramCache]: Analyzing trace with hash 1448466508, now seen corresponding path program 3 times [2025-03-03 15:59:03,304 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 15:59:03,304 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [134625476] [2025-03-03 15:59:03,304 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-03 15:59:03,304 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 15:59:03,309 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 22 statements into 6 equivalence classes. [2025-03-03 15:59:03,328 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 22 of 22 statements. [2025-03-03 15:59:03,329 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-03-03 15:59:03,329 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 15:59:03,330 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1656855155] [2025-03-03 15:59:03,333 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-03 15:59:03,333 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 15:59:03,333 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 15:59:03,335 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:59:03,336 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:59:03,363 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 22 statements into 6 equivalence classes. [2025-03-03 15:59:03,375 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) and asserted 18 of 22 statements. [2025-03-03 15:59:03,375 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2025-03-03 15:59:03,375 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 15:59:03,377 INFO L256 TraceCheckSpWp]: Trace formula consists of 84 conjuncts, 24 conjuncts are in the unsatisfiable core [2025-03-03 15:59:03,378 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 15:59:03,482 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:59:03,482 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 15:59:03,738 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:59:03,738 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 15:59:03,738 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [134625476] [2025-03-03 15:59:03,739 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 15:59:03,739 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1656855155] [2025-03-03 15:59:03,739 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1656855155] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 15:59:03,739 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 15:59:03,739 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 16 [2025-03-03 15:59:03,739 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1900064543] [2025-03-03 15:59:03,739 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 15:59:03,739 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-03-03 15:59:03,739 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 15:59:03,740 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-03-03 15:59:03,740 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=37, Invalid=203, Unknown=0, NotChecked=0, Total=240 [2025-03-03 15:59:03,740 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:59:04,063 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 15:59:04,064 INFO L93 Difference]: Finished difference Result 69 states and 83 transitions. [2025-03-03 15:59:04,064 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2025-03-03 15:59:04,064 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:59:04,064 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 15:59:04,065 INFO L225 Difference]: With dead ends: 69 [2025-03-03 15:59:04,065 INFO L226 Difference]: Without dead ends: 66 [2025-03-03 15:59:04,065 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:59:04,066 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:59:04,066 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:59:04,066 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 66 states. [2025-03-03 15:59:04,076 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 66 to 63. [2025-03-03 15:59:04,077 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:59:04,077 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 75 transitions. [2025-03-03 15:59:04,077 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 75 transitions. Word has length 22 [2025-03-03 15:59:04,078 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 15:59:04,078 INFO L471 AbstractCegarLoop]: Abstraction has 63 states and 75 transitions. [2025-03-03 15:59:04,078 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:59:04,078 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 75 transitions. [2025-03-03 15:59:04,078 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2025-03-03 15:59:04,078 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 15:59:04,078 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:04,086 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:59:04,280 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:59:04,281 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 15:59:04,282 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 15:59:04,282 INFO L85 PathProgramCache]: Analyzing trace with hash 1155762721, now seen corresponding path program 1 times [2025-03-03 15:59:04,282 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 15:59:04,282 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1764128087] [2025-03-03 15:59:04,282 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 15:59:04,282 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 15:59:04,287 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 25 statements into 1 equivalence classes. [2025-03-03 15:59:04,289 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 25 of 25 statements. [2025-03-03 15:59:04,290 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 15:59:04,290 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-03 15:59:04,290 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-03 15:59:04,291 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 25 statements into 1 equivalence classes. [2025-03-03 15:59:04,297 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 25 of 25 statements. [2025-03-03 15:59:04,297 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 15:59:04,297 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-03 15:59:04,307 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-03 15:59:04,309 INFO L340 BasicCegarLoop]: Counterexample is feasible [2025-03-03 15:59:04,309 INFO L782 garLoopResultBuilder]: Registering result UNSAFE for location ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION (1 of 2 remaining) [2025-03-03 15:59:04,310 INFO L782 garLoopResultBuilder]: Registering result UNKNOWN for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 2 remaining) [2025-03-03 15:59:04,311 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2025-03-03 15:59:04,313 INFO L422 BasicCegarLoop]: Path program histogram: [3, 1, 1, 1, 1] [2025-03-03 15:59:04,327 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2025-03-03 15:59:04,329 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 03.03 03:59:04 BoogieIcfgContainer [2025-03-03 15:59:04,330 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2025-03-03 15:59:04,330 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2025-03-03 15:59:04,330 INFO L270 PluginConnector]: Initializing Witness Printer... [2025-03-03 15:59:04,330 INFO L274 PluginConnector]: Witness Printer initialized [2025-03-03 15:59:04,331 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 03:59:01" (3/4) ... [2025-03-03 15:59:04,332 INFO L149 WitnessPrinter]: No result that supports witness generation found [2025-03-03 15:59:04,333 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2025-03-03 15:59:04,334 INFO L158 Benchmark]: Toolchain (without parser) took 3495.92ms. Allocated memory is still 142.6MB. Free memory was 113.1MB in the beginning and 92.1MB in the end (delta: 21.0MB). Peak memory consumption was 17.5MB. Max. memory is 16.1GB. [2025-03-03 15:59:04,336 INFO L158 Benchmark]: CDTParser took 0.21ms. Allocated memory is still 201.3MB. Free memory is still 126.7MB. There was no memory consumed. Max. memory is 16.1GB. [2025-03-03 15:59:04,336 INFO L158 Benchmark]: CACSL2BoogieTranslator took 159.99ms. Allocated memory is still 142.6MB. Free memory was 112.6MB in the beginning and 100.9MB in the end (delta: 11.7MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-03 15:59:04,336 INFO L158 Benchmark]: Boogie Procedure Inliner took 26.87ms. Allocated memory is still 142.6MB. Free memory was 100.9MB in the beginning and 99.6MB in the end (delta: 1.3MB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-03 15:59:04,336 INFO L158 Benchmark]: Boogie Preprocessor took 37.24ms. Allocated memory is still 142.6MB. Free memory was 99.6MB in the beginning and 98.0MB in the end (delta: 1.7MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-03 15:59:04,337 INFO L158 Benchmark]: IcfgBuilder took 232.97ms. Allocated memory is still 142.6MB. Free memory was 98.0MB in the beginning and 84.2MB in the end (delta: 13.7MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-03 15:59:04,337 INFO L158 Benchmark]: TraceAbstraction took 3030.37ms. Allocated memory is still 142.6MB. Free memory was 83.3MB in the beginning and 92.1MB in the end (delta: -8.8MB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-03 15:59:04,337 INFO L158 Benchmark]: Witness Printer took 3.70ms. Allocated memory is still 142.6MB. Free memory was 92.1MB in the beginning and 92.1MB in the end (delta: 41.6kB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-03 15:59:04,338 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.21ms. Allocated memory is still 201.3MB. Free memory is still 126.7MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 159.99ms. Allocated memory is still 142.6MB. Free memory was 112.6MB in the beginning and 100.9MB in the end (delta: 11.7MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 26.87ms. Allocated memory is still 142.6MB. Free memory was 100.9MB in the beginning and 99.6MB in the end (delta: 1.3MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 37.24ms. Allocated memory is still 142.6MB. Free memory was 99.6MB in the beginning and 98.0MB in the end (delta: 1.7MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * IcfgBuilder took 232.97ms. Allocated memory is still 142.6MB. Free memory was 98.0MB in the beginning and 84.2MB in the end (delta: 13.7MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * TraceAbstraction took 3030.37ms. Allocated memory is still 142.6MB. Free memory was 83.3MB in the beginning and 92.1MB in the end (delta: -8.8MB). There was no memory consumed. Max. memory is 16.1GB. * Witness Printer took 3.70ms. Allocated memory is still 142.6MB. Free memory was 92.1MB in the beginning and 92.1MB in the end (delta: 41.6kB). 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 87, overapproximation of someBinaryArithmeticFLOAToperation at line 102, 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 > -2.0f && IN < 2.0f) [L82] COND FALSE !(!cond) [L98] RET assume_abort_if_not(IN > -2.0f && IN < 2.0f) [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: 3.0s, 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.3s 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.1s 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:59:04,350 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_8.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 131b2ae9424ecd75292a5889f04853eea3cca0c3e4c679243c4666d6f4003ffe --- Real Ultimate output --- This is Ultimate 0.3.0-?-798a7b3-m [2025-03-03 15:59:06,169 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-03 15:59:06,244 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Bitvector.epf [2025-03-03 15:59:06,249 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-03 15:59:06,250 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-03 15:59:06,270 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-03 15:59:06,272 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-03 15:59:06,272 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-03 15:59:06,272 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-03 15:59:06,273 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-03 15:59:06,273 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-03 15:59:06,273 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-03 15:59:06,274 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-03 15:59:06,274 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-03 15:59:06,274 INFO L153 SettingsManager]: * Use SBE=true [2025-03-03 15:59:06,274 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-03 15:59:06,274 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-03 15:59:06,274 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-03 15:59:06,275 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-03 15:59:06,275 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-03 15:59:06,275 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-03 15:59:06,275 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-03 15:59:06,275 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-03 15:59:06,275 INFO L153 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2025-03-03 15:59:06,275 INFO L153 SettingsManager]: * Use bitvectors instead of ints=true [2025-03-03 15:59:06,275 INFO L153 SettingsManager]: * Memory model=HoenickeLindenmann_4ByteResolution [2025-03-03 15:59:06,275 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-03 15:59:06,276 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-03 15:59:06,276 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-03 15:59:06,276 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-03 15:59:06,276 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-03 15:59:06,276 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-03 15:59:06,277 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-03 15:59:06,277 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-03 15:59:06,277 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 15:59:06,277 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-03 15:59:06,277 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-03 15:59:06,277 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-03 15:59:06,277 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-03 15:59:06,277 INFO L153 SettingsManager]: * Trace refinement strategy=FOX [2025-03-03 15:59:06,277 INFO L153 SettingsManager]: * Command for external solver=cvc4 --incremental --print-success --lang smt [2025-03-03 15:59:06,277 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-03 15:59:06,277 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-03 15:59:06,277 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-03 15:59:06,277 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-03 15:59:06,277 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 -> 131b2ae9424ecd75292a5889f04853eea3cca0c3e4c679243c4666d6f4003ffe [2025-03-03 15:59:06,526 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-03 15:59:06,533 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-03 15:59:06,534 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-03 15:59:06,535 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-03 15:59:06,535 INFO L274 PluginConnector]: CDTParser initialized [2025-03-03 15:59:06,538 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/combinations/gcd_4+newton_2_8.i [2025-03-03 15:59:07,673 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/9175171ea/5ba8f6f97b00430790c8f0d0923cb6e6/FLAGb0c86f1a0 [2025-03-03 15:59:07,881 INFO L384 CDTParser]: Found 1 translation units. [2025-03-03 15:59:07,882 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/combinations/gcd_4+newton_2_8.i [2025-03-03 15:59:07,889 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/9175171ea/5ba8f6f97b00430790c8f0d0923cb6e6/FLAGb0c86f1a0 [2025-03-03 15:59:08,245 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/9175171ea/5ba8f6f97b00430790c8f0d0923cb6e6 [2025-03-03 15:59:08,246 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-03 15:59:08,247 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-03 15:59:08,248 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-03 15:59:08,248 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-03 15:59:08,251 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-03 15:59:08,251 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 03:59:08" (1/1) ... [2025-03-03 15:59:08,252 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@10672e29 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:59:08, skipping insertion in model container [2025-03-03 15:59:08,252 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 03:59:08" (1/1) ... [2025-03-03 15:59:08,261 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-03 15:59:08,350 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_8.i[1224,1237] [2025-03-03 15:59:08,371 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_8.i[2827,2840] [2025-03-03 15:59:08,372 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 15:59:08,381 INFO L200 MainTranslator]: Completed pre-run [2025-03-03 15:59:08,389 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_8.i[1224,1237] [2025-03-03 15:59:08,398 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_8.i[2827,2840] [2025-03-03 15:59:08,399 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 15:59:08,412 INFO L204 MainTranslator]: Completed translation [2025-03-03 15:59:08,412 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:59:08 WrapperNode [2025-03-03 15:59:08,413 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-03 15:59:08,413 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-03 15:59:08,414 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-03 15:59:08,414 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-03 15:59:08,418 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:59:08" (1/1) ... [2025-03-03 15:59:08,424 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:59:08" (1/1) ... [2025-03-03 15:59:08,438 INFO L138 Inliner]: procedures = 28, calls = 26, calls flagged for inlining = 6, calls inlined = 6, statements flattened = 73 [2025-03-03 15:59:08,438 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-03 15:59:08,438 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-03 15:59:08,438 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-03 15:59:08,439 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-03 15:59:08,444 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:59:08" (1/1) ... [2025-03-03 15:59:08,444 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:59:08" (1/1) ... [2025-03-03 15:59:08,446 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:59:08" (1/1) ... [2025-03-03 15:59:08,454 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:59:08,454 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:59:08" (1/1) ... [2025-03-03 15:59:08,454 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:59:08" (1/1) ... [2025-03-03 15:59:08,464 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:59:08" (1/1) ... [2025-03-03 15:59:08,465 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:59:08" (1/1) ... [2025-03-03 15:59:08,468 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:59:08" (1/1) ... [2025-03-03 15:59:08,468 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:59:08" (1/1) ... [2025-03-03 15:59:08,470 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-03 15:59:08,471 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-03 15:59:08,471 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-03 15:59:08,471 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-03 15:59:08,472 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:59:08" (1/1) ... [2025-03-03 15:59:08,476 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 15:59:08,486 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 15:59:08,498 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:59:08,502 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:59:08,521 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-03 15:59:08,521 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#0 [2025-03-03 15:59:08,522 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#1 [2025-03-03 15:59:08,522 INFO L130 BoogieDeclarations]: Found specification of procedure fp [2025-03-03 15:59:08,522 INFO L138 BoogieDeclarations]: Found implementation of procedure fp [2025-03-03 15:59:08,522 INFO L130 BoogieDeclarations]: Found specification of procedure f [2025-03-03 15:59:08,522 INFO L138 BoogieDeclarations]: Found implementation of procedure f [2025-03-03 15:59:08,522 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-03 15:59:08,522 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-03 15:59:08,522 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-03-03 15:59:08,522 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-03-03 15:59:08,579 INFO L256 CfgBuilder]: Building ICFG [2025-03-03 15:59:08,581 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-03 15:59:19,712 INFO L? ?]: Removed 22 outVars from TransFormulas that were not future-live. [2025-03-03 15:59:19,714 INFO L307 CfgBuilder]: Performing block encoding [2025-03-03 15:59:19,721 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-03 15:59:19,722 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-03 15:59:19,722 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 03:59:19 BoogieIcfgContainer [2025-03-03 15:59:19,723 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-03 15:59:19,725 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-03 15:59:19,725 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-03 15:59:19,729 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-03 15:59:19,729 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 03.03 03:59:08" (1/3) ... [2025-03-03 15:59:19,730 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@66a54f41 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 03:59:19, skipping insertion in model container [2025-03-03 15:59:19,730 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 03:59:08" (2/3) ... [2025-03-03 15:59:19,730 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@66a54f41 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 03:59:19, skipping insertion in model container [2025-03-03 15:59:19,730 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 03:59:19" (3/3) ... [2025-03-03 15:59:19,732 INFO L128 eAbstractionObserver]: Analyzing ICFG gcd_4+newton_2_8.i [2025-03-03 15:59:19,741 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-03 15:59:19,743 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG gcd_4+newton_2_8.i that has 4 procedures, 42 locations, 1 initial locations, 1 loop locations, and 2 error locations. [2025-03-03 15:59:19,785 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-03 15:59:19,794 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;@1d0042f, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-03 15:59:19,795 INFO L334 AbstractCegarLoop]: Starting to check reachability of 2 error locations. [2025-03-03 15:59:19,798 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:59:19,802 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2025-03-03 15:59:19,802 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 15:59:19,803 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 15:59:19,803 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 15:59:19,807 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 15:59:19,808 INFO L85 PathProgramCache]: Analyzing trace with hash -1151646490, now seen corresponding path program 1 times [2025-03-03 15:59:19,814 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-03-03 15:59:19,816 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2032968073] [2025-03-03 15:59:19,816 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 15:59:19,817 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 15:59:19,817 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 15:59:19,819 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:59:19,821 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:59:19,877 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 11 statements into 1 equivalence classes. [2025-03-03 15:59:19,911 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 11 of 11 statements. [2025-03-03 15:59:19,911 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 15:59:19,911 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 15:59:19,915 INFO L256 TraceCheckSpWp]: Trace formula consists of 42 conjuncts, 4 conjuncts are in the unsatisfiable core [2025-03-03 15:59:19,918 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 15:59:20,015 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:59:20,015 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-03 15:59:20,015 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-03-03 15:59:20,015 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2032968073] [2025-03-03 15:59:20,016 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2032968073] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 15:59:20,016 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 15:59:20,016 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2025-03-03 15:59:20,017 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1896493952] [2025-03-03 15:59:20,017 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 15:59:20,019 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2025-03-03 15:59:20,019 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-03-03 15:59:20,030 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2025-03-03 15:59:20,031 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-03-03 15:59:20,032 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:59:20,148 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 15:59:20,149 INFO L93 Difference]: Finished difference Result 81 states and 107 transitions. [2025-03-03 15:59:20,150 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2025-03-03 15:59:20,151 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:59:20,151 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 15:59:20,154 INFO L225 Difference]: With dead ends: 81 [2025-03-03 15:59:20,154 INFO L226 Difference]: Without dead ends: 37 [2025-03-03 15:59:20,156 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:59:20,158 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:59:20,159 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:59:20,168 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2025-03-03 15:59:20,177 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 35. [2025-03-03 15:59:20,178 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:59:20,180 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 41 transitions. [2025-03-03 15:59:20,181 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 41 transitions. Word has length 11 [2025-03-03 15:59:20,181 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 15:59:20,181 INFO L471 AbstractCegarLoop]: Abstraction has 35 states and 41 transitions. [2025-03-03 15:59:20,181 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:59:20,182 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 41 transitions. [2025-03-03 15:59:20,182 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2025-03-03 15:59:20,182 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 15:59:20,182 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 15:59:20,191 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2025-03-03 15:59:20,383 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:59:20,383 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 15:59:20,384 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 15:59:20,384 INFO L85 PathProgramCache]: Analyzing trace with hash 2048670773, now seen corresponding path program 1 times [2025-03-03 15:59:20,384 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-03-03 15:59:20,384 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1083063235] [2025-03-03 15:59:20,384 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 15:59:20,384 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 15:59:20,384 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 15:59:20,387 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:59:20,388 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:59:20,417 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 12 statements into 1 equivalence classes. [2025-03-03 15:59:20,432 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 12 of 12 statements. [2025-03-03 15:59:20,432 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 15:59:20,432 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 15:59:20,436 INFO L256 TraceCheckSpWp]: Trace formula consists of 42 conjuncts, 4 conjuncts are in the unsatisfiable core [2025-03-03 15:59:20,437 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 15:59:20,514 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:59:20,514 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-03 15:59:20,514 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-03-03 15:59:20,515 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1083063235] [2025-03-03 15:59:20,515 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1083063235] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 15:59:20,515 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 15:59:20,515 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2025-03-03 15:59:20,515 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1473932766] [2025-03-03 15:59:20,515 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 15:59:20,516 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2025-03-03 15:59:20,516 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-03-03 15:59:20,516 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2025-03-03 15:59:20,516 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-03-03 15:59:20,516 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:59:20,624 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 15:59:20,624 INFO L93 Difference]: Finished difference Result 50 states and 61 transitions. [2025-03-03 15:59:20,625 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2025-03-03 15:59:20,625 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:59:20,625 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 15:59:20,625 INFO L225 Difference]: With dead ends: 50 [2025-03-03 15:59:20,625 INFO L226 Difference]: Without dead ends: 37 [2025-03-03 15:59:20,626 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:59:20,626 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:59:20,627 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:59:20,627 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2025-03-03 15:59:20,630 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 37. [2025-03-03 15:59:20,630 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:59:20,630 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 43 transitions. [2025-03-03 15:59:20,631 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 43 transitions. Word has length 12 [2025-03-03 15:59:20,631 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 15:59:20,631 INFO L471 AbstractCegarLoop]: Abstraction has 37 states and 43 transitions. [2025-03-03 15:59:20,631 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:59:20,631 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 43 transitions. [2025-03-03 15:59:20,631 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2025-03-03 15:59:20,631 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 15:59:20,631 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 15:59:20,639 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:59:20,832 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:59:20,832 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 15:59:20,833 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 15:59:20,833 INFO L85 PathProgramCache]: Analyzing trace with hash 373208147, now seen corresponding path program 1 times [2025-03-03 15:59:20,833 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-03-03 15:59:20,833 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1834581954] [2025-03-03 15:59:20,833 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 15:59:20,835 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 15:59:20,835 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 15:59:20,836 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:59:20,837 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:59:20,866 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 14 statements into 1 equivalence classes. [2025-03-03 15:59:20,882 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 14 of 14 statements. [2025-03-03 15:59:20,883 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 15:59:20,883 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 15:59:20,886 INFO L256 TraceCheckSpWp]: Trace formula consists of 44 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-03 15:59:20,887 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 15:59:21,245 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:59:21,245 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 15:59:21,506 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:59:21,506 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-03-03 15:59:21,506 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1834581954] [2025-03-03 15:59:21,506 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1834581954] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 15:59:21,506 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 15:59:21,506 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 6 [2025-03-03 15:59:21,506 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [652689606] [2025-03-03 15:59:21,506 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 15:59:21,506 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-03-03 15:59:21,507 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-03-03 15:59:21,507 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-03 15:59:21,507 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2025-03-03 15:59:21,507 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:59:21,853 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 15:59:21,854 INFO L93 Difference]: Finished difference Result 54 states and 66 transitions. [2025-03-03 15:59:21,854 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-03 15:59:21,854 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:59:21,854 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 15:59:21,855 INFO L225 Difference]: With dead ends: 54 [2025-03-03 15:59:21,855 INFO L226 Difference]: Without dead ends: 42 [2025-03-03 15:59:21,855 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 27 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2025-03-03 15:59:21,856 INFO L435 NwaCegarLoop]: 34 mSDtfsCounter, 5 mSDsluCounter, 93 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s 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:59:21,856 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:59:21,856 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2025-03-03 15:59:21,859 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 40. [2025-03-03 15:59:21,860 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:59:21,860 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 46 transitions. [2025-03-03 15:59:21,860 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 46 transitions. Word has length 14 [2025-03-03 15:59:21,861 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 15:59:21,861 INFO L471 AbstractCegarLoop]: Abstraction has 40 states and 46 transitions. [2025-03-03 15:59:21,861 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:59:21,861 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 46 transitions. [2025-03-03 15:59:21,861 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2025-03-03 15:59:21,861 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 15:59:21,861 INFO L218 NwaCegarLoop]: trace histogram [3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 15:59:21,868 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:59:22,062 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:59:22,062 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 15:59:22,062 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 15:59:22,063 INFO L85 PathProgramCache]: Analyzing trace with hash 1716297167, now seen corresponding path program 1 times [2025-03-03 15:59:22,063 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-03-03 15:59:22,063 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1627394318] [2025-03-03 15:59:22,063 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 15:59:22,063 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 15:59:22,063 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 15:59:22,066 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:59:22,066 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:59:22,089 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 18 statements into 1 equivalence classes. [2025-03-03 15:59:22,106 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 18 of 18 statements. [2025-03-03 15:59:22,106 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 15:59:22,106 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 15:59:22,111 INFO L256 TraceCheckSpWp]: Trace formula consists of 50 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-03-03 15:59:22,113 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 15:59:22,841 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:59:22,842 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 15:59:23,473 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:59:23,474 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-03-03 15:59:23,474 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1627394318] [2025-03-03 15:59:23,474 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1627394318] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 15:59:23,474 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 15:59:23,474 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2025-03-03 15:59:23,474 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [245828505] [2025-03-03 15:59:23,474 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 15:59:23,474 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-03-03 15:59:23,474 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-03-03 15:59:23,475 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-03-03 15:59:23,475 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=60, Unknown=0, NotChecked=0, Total=90 [2025-03-03 15:59:23,475 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:59:24,515 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 15:59:24,515 INFO L93 Difference]: Finished difference Result 62 states and 76 transitions. [2025-03-03 15:59:24,516 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-03 15:59:24,516 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:59:24,516 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 15:59:24,516 INFO L225 Difference]: With dead ends: 62 [2025-03-03 15:59:24,516 INFO L226 Difference]: Without dead ends: 49 [2025-03-03 15:59:24,517 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 37 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=57, Invalid=99, Unknown=0, NotChecked=0, Total=156 [2025-03-03 15:59:24,517 INFO L435 NwaCegarLoop]: 34 mSDtfsCounter, 7 mSDsluCounter, 155 mSDsCounter, 0 mSdLazyCounter, 65 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s 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.6s IncrementalHoareTripleChecker+Time [2025-03-03 15:59:24,517 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.6s Time] [2025-03-03 15:59:24,518 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2025-03-03 15:59:24,521 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 48. [2025-03-03 15:59:24,521 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:59:24,522 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 56 transitions. [2025-03-03 15:59:24,522 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 56 transitions. Word has length 18 [2025-03-03 15:59:24,522 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 15:59:24,522 INFO L471 AbstractCegarLoop]: Abstraction has 48 states and 56 transitions. [2025-03-03 15:59:24,522 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:59:24,522 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 56 transitions. [2025-03-03 15:59:24,523 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2025-03-03 15:59:24,523 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 15:59:24,523 INFO L218 NwaCegarLoop]: trace histogram [5, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 15:59:24,530 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:59:24,723 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:59:24,723 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 15:59:24,724 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 15:59:24,724 INFO L85 PathProgramCache]: Analyzing trace with hash 1448466508, now seen corresponding path program 2 times [2025-03-03 15:59:24,724 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-03-03 15:59:24,724 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1021638158] [2025-03-03 15:59:24,725 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 15:59:24,725 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 15:59:24,725 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 15:59:24,727 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:59:24,728 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:59:24,753 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 22 statements into 2 equivalence classes. [2025-03-03 15:59:24,777 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 22 of 22 statements. [2025-03-03 15:59:24,777 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 15:59:24,777 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 15:59:24,782 INFO L256 TraceCheckSpWp]: Trace formula consists of 56 conjuncts, 18 conjuncts are in the unsatisfiable core [2025-03-03 15:59:24,783 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 15:59:26,605 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:59:26,606 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 15:59:36,951 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:59:36,951 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-03-03 15:59:36,951 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1021638158] [2025-03-03 15:59:36,951 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1021638158] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 15:59:36,951 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 15:59:36,952 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 12] total 20 [2025-03-03 15:59:36,952 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1569121956] [2025-03-03 15:59:36,952 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 15:59:36,952 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2025-03-03 15:59:36,952 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-03-03 15:59:36,953 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2025-03-03 15:59:36,953 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=322, Unknown=0, NotChecked=0, Total=380 [2025-03-03 15:59:36,953 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:48,903 WARN L286 SmtUtils]: Spent 7.03s 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:53,394 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.04s for a HTC check with result UNKNOWN. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2025-03-03 15:59:57,402 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 16:00:01,410 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 16:00:13,868 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 16:00:18,180 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.03s for a HTC check with result UNKNOWN. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2025-03-03 16:00:22,188 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 16:00:25,215 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 3.03s for a HTC check with result INVALID. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2025-03-03 16:00:29,223 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 16:00:37,097 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.07s for a HTC check with result INVALID. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2025-03-03 16:00:38,588 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.15s for a HTC check with result INVALID. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2025-03-03 16:00:40,638 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 16:00:40,638 INFO L93 Difference]: Finished difference Result 70 states and 86 transitions. [2025-03-03 16:00:40,642 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2025-03-03 16:00:40,643 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 16:00:40,643 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 16:00:40,643 INFO L225 Difference]: With dead ends: 70 [2025-03-03 16:00:40,643 INFO L226 Difference]: Without dead ends: 67 [2025-03-03 16:00:40,644 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 24 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 45 ImplicationChecksByTransitivity, 33.3s TimeCoverageRelationStatistics Valid=96, Invalid=504, Unknown=0, NotChecked=0, Total=600 [2025-03-03 16:00:40,644 INFO L435 NwaCegarLoop]: 31 mSDtfsCounter, 6 mSDsluCounter, 408 mSDsCounter, 0 mSdLazyCounter, 246 mSolverCounterSat, 9 mSolverCounterUnsat, 7 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 38.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 439 SdHoareTripleChecker+Invalid, 262 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 246 IncrementalHoareTripleChecker+Invalid, 7 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 39.4s IncrementalHoareTripleChecker+Time [2025-03-03 16:00:40,644 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 439 Invalid, 262 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 246 Invalid, 7 Unknown, 0 Unchecked, 39.4s Time] [2025-03-03 16:00:40,645 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2025-03-03 16:00:40,651 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 65. [2025-03-03 16:00:40,652 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 16:00:40,654 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 65 states to 65 states and 79 transitions. [2025-03-03 16:00:40,654 INFO L78 Accepts]: Start accepts. Automaton has 65 states and 79 transitions. Word has length 22 [2025-03-03 16:00:40,654 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 16:00:40,655 INFO L471 AbstractCegarLoop]: Abstraction has 65 states and 79 transitions. [2025-03-03 16:00:40,655 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 16:00:40,655 INFO L276 IsEmpty]: Start isEmpty. Operand 65 states and 79 transitions. [2025-03-03 16:00:40,655 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2025-03-03 16:00:40,655 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 16:00:40,656 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 16:00:40,664 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 16:00:40,856 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 16:00:40,856 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 16:00:40,857 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 16:00:40,857 INFO L85 PathProgramCache]: Analyzing trace with hash 1155762721, now seen corresponding path program 1 times [2025-03-03 16:00:40,857 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-03-03 16:00:40,857 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [2118666952] [2025-03-03 16:00:40,857 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 16:00:40,857 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 16:00:40,857 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2025-03-03 16:00:40,859 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 16:00:40,860 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 16:00:40,874 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 25 statements into 1 equivalence classes.