./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench/egcd3-ll.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 8fc3dc66 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/nla-digbench/egcd3-ll.c -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 4ef08007570a64191e0df13d14d3e8d62a8022f43f46779ea6f6701a621376be --- Real Ultimate output --- This is Ultimate 0.3.0-?-8fc3dc6-m [2025-03-16 18:00:17,329 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-16 18:00:17,436 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-16 18:00:17,445 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-16 18:00:17,450 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-16 18:00:17,482 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-16 18:00:17,488 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-16 18:00:17,488 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-16 18:00:17,488 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-16 18:00:17,488 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-16 18:00:17,488 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-16 18:00:17,488 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-16 18:00:17,489 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-16 18:00:17,489 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-16 18:00:17,489 INFO L153 SettingsManager]: * Use SBE=true [2025-03-16 18:00:17,489 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-16 18:00:17,489 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-16 18:00:17,489 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-16 18:00:17,489 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-16 18:00:17,489 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-16 18:00:17,489 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-16 18:00:17,489 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-16 18:00:17,489 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-16 18:00:17,489 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-16 18:00:17,489 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-16 18:00:17,489 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-16 18:00:17,489 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-16 18:00:17,489 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-16 18:00:17,490 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-16 18:00:17,490 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-16 18:00:17,490 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-16 18:00:17,490 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-16 18:00:17,490 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-16 18:00:17,490 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-16 18:00:17,490 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-16 18:00:17,490 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-16 18:00:17,490 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-16 18:00:17,490 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-16 18:00:17,490 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-16 18:00:17,490 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-16 18:00:17,490 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-16 18:00:17,490 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-16 18:00:17,490 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-16 18:00:17,490 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 -> 4ef08007570a64191e0df13d14d3e8d62a8022f43f46779ea6f6701a621376be [2025-03-16 18:00:17,965 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-16 18:00:17,982 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-16 18:00:17,983 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-16 18:00:17,989 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-16 18:00:17,990 INFO L274 PluginConnector]: CDTParser initialized [2025-03-16 18:00:17,991 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench/egcd3-ll.c [2025-03-16 18:00:19,628 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/6a46ce327/80930c52052a464a988b03093881f2be/FLAG0e3315dc7 [2025-03-16 18:00:20,018 INFO L384 CDTParser]: Found 1 translation units. [2025-03-16 18:00:20,020 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench/egcd3-ll.c [2025-03-16 18:00:20,029 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/6a46ce327/80930c52052a464a988b03093881f2be/FLAG0e3315dc7 [2025-03-16 18:00:20,052 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/6a46ce327/80930c52052a464a988b03093881f2be [2025-03-16 18:00:20,056 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-16 18:00:20,058 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-16 18:00:20,059 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-16 18:00:20,060 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-16 18:00:20,064 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-16 18:00:20,068 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.03 06:00:20" (1/1) ... [2025-03-16 18:00:20,069 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@46aa24a8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:00:20, skipping insertion in model container [2025-03-16 18:00:20,070 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.03 06:00:20" (1/1) ... [2025-03-16 18:00:20,095 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-16 18:00:20,261 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/nla-digbench/egcd3-ll.c[490,503] [2025-03-16 18:00:20,293 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-16 18:00:20,310 INFO L200 MainTranslator]: Completed pre-run [2025-03-16 18:00:20,325 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/nla-digbench/egcd3-ll.c[490,503] [2025-03-16 18:00:20,338 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-16 18:00:20,355 INFO L204 MainTranslator]: Completed translation [2025-03-16 18:00:20,356 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:00:20 WrapperNode [2025-03-16 18:00:20,356 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-16 18:00:20,358 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-16 18:00:20,358 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-16 18:00:20,358 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-16 18:00:20,370 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:00:20" (1/1) ... [2025-03-16 18:00:20,385 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:00:20" (1/1) ... [2025-03-16 18:00:20,408 INFO L138 Inliner]: procedures = 14, calls = 14, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 72 [2025-03-16 18:00:20,410 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-16 18:00:20,410 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-16 18:00:20,411 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-16 18:00:20,411 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-16 18:00:20,421 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:00:20" (1/1) ... [2025-03-16 18:00:20,424 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:00:20" (1/1) ... [2025-03-16 18:00:20,425 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:00:20" (1/1) ... [2025-03-16 18:00:20,447 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2025-03-16 18:00:20,447 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:00:20" (1/1) ... [2025-03-16 18:00:20,447 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:00:20" (1/1) ... [2025-03-16 18:00:20,455 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:00:20" (1/1) ... [2025-03-16 18:00:20,455 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:00:20" (1/1) ... [2025-03-16 18:00:20,456 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:00:20" (1/1) ... [2025-03-16 18:00:20,456 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:00:20" (1/1) ... [2025-03-16 18:00:20,457 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-16 18:00:20,465 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-16 18:00:20,465 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-16 18:00:20,465 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-16 18:00:20,466 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:00:20" (1/1) ... [2025-03-16 18:00:20,475 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-16 18:00:20,493 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:00:20,523 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-16 18:00:20,527 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-16 18:00:20,558 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-16 18:00:20,559 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2025-03-16 18:00:20,559 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2025-03-16 18:00:20,559 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-16 18:00:20,559 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-16 18:00:20,559 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-16 18:00:20,559 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-03-16 18:00:20,559 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-03-16 18:00:20,637 INFO L256 CfgBuilder]: Building ICFG [2025-03-16 18:00:20,642 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-16 18:00:20,873 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2025-03-16 18:00:20,874 INFO L307 CfgBuilder]: Performing block encoding [2025-03-16 18:00:20,889 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-16 18:00:20,889 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-16 18:00:20,889 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.03 06:00:20 BoogieIcfgContainer [2025-03-16 18:00:20,890 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-16 18:00:20,895 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-16 18:00:20,895 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-16 18:00:20,900 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-16 18:00:20,903 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 16.03 06:00:20" (1/3) ... [2025-03-16 18:00:20,904 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5518aac7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.03 06:00:20, skipping insertion in model container [2025-03-16 18:00:20,904 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:00:20" (2/3) ... [2025-03-16 18:00:20,904 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5518aac7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.03 06:00:20, skipping insertion in model container [2025-03-16 18:00:20,904 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.03 06:00:20" (3/3) ... [2025-03-16 18:00:20,906 INFO L128 eAbstractionObserver]: Analyzing ICFG egcd3-ll.c [2025-03-16 18:00:20,929 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-16 18:00:20,932 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG egcd3-ll.c that has 3 procedures, 27 locations, 1 initial locations, 3 loop locations, and 1 error locations. [2025-03-16 18:00:21,011 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-16 18:00:21,032 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;@369593e2, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-16 18:00:21,035 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-16 18:00:21,041 INFO L276 IsEmpty]: Start isEmpty. Operand has 27 states, 17 states have (on average 1.4705882352941178) internal successors, (25), 17 states have internal predecessors, (25), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2025-03-16 18:00:21,053 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2025-03-16 18:00:21,053 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:00:21,054 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:00:21,054 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:00:21,062 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:00:21,063 INFO L85 PathProgramCache]: Analyzing trace with hash 1245034254, now seen corresponding path program 1 times [2025-03-16 18:00:21,073 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:00:21,077 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [241835116] [2025-03-16 18:00:21,079 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:00:21,080 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:00:21,181 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 17 statements into 1 equivalence classes. [2025-03-16 18:00:21,205 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 17 of 17 statements. [2025-03-16 18:00:21,206 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:00:21,206 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:00:21,282 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2025-03-16 18:00:21,286 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:00:21,286 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [241835116] [2025-03-16 18:00:21,287 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [241835116] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:00:21,288 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1675512067] [2025-03-16 18:00:21,288 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:00:21,288 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:00:21,288 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:00:21,294 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-16 18:00:21,296 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-16 18:00:21,371 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 17 statements into 1 equivalence classes. [2025-03-16 18:00:21,400 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 17 of 17 statements. [2025-03-16 18:00:21,400 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:00:21,400 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:00:21,406 INFO L256 TraceCheckSpWp]: Trace formula consists of 66 conjuncts, 1 conjuncts are in the unsatisfiable core [2025-03-16 18:00:21,413 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:00:21,429 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2025-03-16 18:00:21,429 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-16 18:00:21,430 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1675512067] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:00:21,430 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:00:21,431 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2025-03-16 18:00:21,432 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [593748965] [2025-03-16 18:00:21,432 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:00:21,439 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-03-16 18:00:21,439 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:00:21,467 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-03-16 18:00:21,468 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-16 18:00:21,469 INFO L87 Difference]: Start difference. First operand has 27 states, 17 states have (on average 1.4705882352941178) internal successors, (25), 17 states have internal predecessors, (25), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-16 18:00:21,499 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:00:21,502 INFO L93 Difference]: Finished difference Result 52 states and 82 transitions. [2025-03-16 18:00:21,503 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-03-16 18:00:21,508 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 17 [2025-03-16 18:00:21,508 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:00:21,513 INFO L225 Difference]: With dead ends: 52 [2025-03-16 18:00:21,518 INFO L226 Difference]: Without dead ends: 24 [2025-03-16 18:00:21,521 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-16 18:00:21,528 INFO L435 NwaCegarLoop]: 34 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 34 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 18:00:21,531 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 34 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 18:00:21,558 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2025-03-16 18:00:21,583 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2025-03-16 18:00:21,584 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 14 states have (on average 1.2857142857142858) internal successors, (18), 15 states have internal predecessors, (18), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-03-16 18:00:21,592 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 31 transitions. [2025-03-16 18:00:21,595 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 31 transitions. Word has length 17 [2025-03-16 18:00:21,596 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:00:21,596 INFO L471 AbstractCegarLoop]: Abstraction has 24 states and 31 transitions. [2025-03-16 18:00:21,596 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-16 18:00:21,600 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 31 transitions. [2025-03-16 18:00:21,600 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2025-03-16 18:00:21,601 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:00:21,601 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:00:21,613 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-16 18:00:21,801 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,SelfDestructingSolverStorable0 [2025-03-16 18:00:21,802 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:00:21,804 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:00:21,804 INFO L85 PathProgramCache]: Analyzing trace with hash -1067978834, now seen corresponding path program 1 times [2025-03-16 18:00:21,804 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:00:21,805 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [299127944] [2025-03-16 18:00:21,805 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:00:21,805 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:00:21,820 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 17 statements into 1 equivalence classes. [2025-03-16 18:00:21,850 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 17 of 17 statements. [2025-03-16 18:00:21,852 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:00:21,852 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:00:22,135 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-03-16 18:00:22,136 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:00:22,136 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [299127944] [2025-03-16 18:00:22,136 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [299127944] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:00:22,136 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:00:22,136 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2025-03-16 18:00:22,136 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [332042092] [2025-03-16 18:00:22,136 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:00:22,141 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-03-16 18:00:22,141 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:00:22,142 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-16 18:00:22,142 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2025-03-16 18:00:22,142 INFO L87 Difference]: Start difference. First operand 24 states and 31 transitions. Second operand has 6 states, 6 states have (on average 2.0) internal successors, (12), 5 states have internal predecessors, (12), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2025-03-16 18:00:22,274 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:00:22,274 INFO L93 Difference]: Finished difference Result 40 states and 53 transitions. [2025-03-16 18:00:22,275 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-16 18:00:22,275 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 5 states have internal predecessors, (12), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2025-03-16 18:00:22,275 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:00:22,275 INFO L225 Difference]: With dead ends: 40 [2025-03-16 18:00:22,275 INFO L226 Difference]: Without dead ends: 33 [2025-03-16 18:00:22,276 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2025-03-16 18:00:22,276 INFO L435 NwaCegarLoop]: 23 mSDtfsCounter, 22 mSDsluCounter, 74 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 97 SdHoareTripleChecker+Invalid, 48 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:00:22,276 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [26 Valid, 97 Invalid, 48 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:00:22,277 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2025-03-16 18:00:22,286 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 25. [2025-03-16 18:00:22,292 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 25 states, 15 states have (on average 1.2666666666666666) internal successors, (19), 16 states have internal predecessors, (19), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-03-16 18:00:22,293 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 32 transitions. [2025-03-16 18:00:22,293 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 32 transitions. Word has length 17 [2025-03-16 18:00:22,293 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:00:22,293 INFO L471 AbstractCegarLoop]: Abstraction has 25 states and 32 transitions. [2025-03-16 18:00:22,293 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 5 states have internal predecessors, (12), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2025-03-16 18:00:22,293 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 32 transitions. [2025-03-16 18:00:22,293 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2025-03-16 18:00:22,293 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:00:22,293 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:00:22,294 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-03-16 18:00:22,294 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:00:22,294 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:00:22,294 INFO L85 PathProgramCache]: Analyzing trace with hash 1289635250, now seen corresponding path program 1 times [2025-03-16 18:00:22,294 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:00:22,294 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1324612502] [2025-03-16 18:00:22,294 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:00:22,294 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:00:22,310 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 18 statements into 1 equivalence classes. [2025-03-16 18:00:22,335 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 18 of 18 statements. [2025-03-16 18:00:22,337 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:00:22,340 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:00:22,342 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [293987955] [2025-03-16 18:00:22,342 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:00:22,342 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:00:22,342 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:00:22,354 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-16 18:00:22,362 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-16 18:00:22,408 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 18 statements into 1 equivalence classes. [2025-03-16 18:00:22,447 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 18 of 18 statements. [2025-03-16 18:00:22,447 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:00:22,447 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:00:22,450 INFO L256 TraceCheckSpWp]: Trace formula consists of 74 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-16 18:00:22,454 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:00:22,650 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-16 18:00:22,650 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-16 18:00:22,650 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:00:22,650 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1324612502] [2025-03-16 18:00:22,650 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:00:22,651 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [293987955] [2025-03-16 18:00:22,651 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [293987955] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:00:22,651 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:00:22,651 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:00:22,651 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1899809943] [2025-03-16 18:00:22,651 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:00:22,651 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:00:22,651 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:00:22,651 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:00:22,651 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:00:22,652 INFO L87 Difference]: Start difference. First operand 25 states and 32 transitions. Second operand has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2025-03-16 18:00:22,731 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:00:22,731 INFO L93 Difference]: Finished difference Result 39 states and 51 transitions. [2025-03-16 18:00:22,733 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 18:00:22,733 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2025-03-16 18:00:22,733 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:00:22,733 INFO L225 Difference]: With dead ends: 39 [2025-03-16 18:00:22,734 INFO L226 Difference]: Without dead ends: 37 [2025-03-16 18:00:22,734 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2025-03-16 18:00:22,735 INFO L435 NwaCegarLoop]: 26 mSDtfsCounter, 7 mSDsluCounter, 72 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 98 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:00:22,739 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 98 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:00:22,739 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2025-03-16 18:00:22,752 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 36. [2025-03-16 18:00:22,752 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 21 states have (on average 1.2857142857142858) internal successors, (27), 22 states have internal predecessors, (27), 11 states have call successors, (11), 3 states have call predecessors, (11), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2025-03-16 18:00:22,754 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 48 transitions. [2025-03-16 18:00:22,754 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 48 transitions. Word has length 18 [2025-03-16 18:00:22,754 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:00:22,758 INFO L471 AbstractCegarLoop]: Abstraction has 36 states and 48 transitions. [2025-03-16 18:00:22,759 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2025-03-16 18:00:22,759 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 48 transitions. [2025-03-16 18:00:22,759 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2025-03-16 18:00:22,759 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:00:22,759 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:00:22,773 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-16 18:00:22,960 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,SelfDestructingSolverStorable2 [2025-03-16 18:00:22,960 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:00:22,964 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:00:22,964 INFO L85 PathProgramCache]: Analyzing trace with hash -661372727, now seen corresponding path program 1 times [2025-03-16 18:00:22,964 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:00:22,964 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [167059352] [2025-03-16 18:00:22,965 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:00:22,965 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:00:22,975 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 20 statements into 1 equivalence classes. [2025-03-16 18:00:22,994 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 20 of 20 statements. [2025-03-16 18:00:22,995 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:00:22,995 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:00:23,219 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-03-16 18:00:23,219 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:00:23,219 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [167059352] [2025-03-16 18:00:23,219 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [167059352] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:00:23,219 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [41905865] [2025-03-16 18:00:23,219 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:00:23,219 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:00:23,219 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:00:23,225 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-16 18:00:23,246 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-16 18:00:23,282 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 20 statements into 1 equivalence classes. [2025-03-16 18:00:23,305 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 20 of 20 statements. [2025-03-16 18:00:23,305 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:00:23,305 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:00:23,309 INFO L256 TraceCheckSpWp]: Trace formula consists of 84 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-16 18:00:23,310 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:00:23,352 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-03-16 18:00:23,357 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:00:23,491 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-03-16 18:00:23,493 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [41905865] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:00:23,495 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:00:23,496 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 9 [2025-03-16 18:00:23,496 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2095658920] [2025-03-16 18:00:23,496 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:00:23,496 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-03-16 18:00:23,496 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:00:23,496 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-16 18:00:23,497 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2025-03-16 18:00:23,497 INFO L87 Difference]: Start difference. First operand 36 states and 48 transitions. Second operand has 9 states, 9 states have (on average 1.8888888888888888) internal successors, (17), 8 states have internal predecessors, (17), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-16 18:00:23,750 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:00:23,750 INFO L93 Difference]: Finished difference Result 78 states and 116 transitions. [2025-03-16 18:00:23,752 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-16 18:00:23,752 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 1.8888888888888888) internal successors, (17), 8 states have internal predecessors, (17), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 20 [2025-03-16 18:00:23,752 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:00:23,753 INFO L225 Difference]: With dead ends: 78 [2025-03-16 18:00:23,753 INFO L226 Difference]: Without dead ends: 71 [2025-03-16 18:00:23,753 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 50 GetRequests, 35 SyntacticMatches, 4 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=42, Invalid=114, Unknown=0, NotChecked=0, Total=156 [2025-03-16 18:00:23,754 INFO L435 NwaCegarLoop]: 28 mSDtfsCounter, 41 mSDsluCounter, 119 mSDsCounter, 0 mSdLazyCounter, 76 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 45 SdHoareTripleChecker+Valid, 147 SdHoareTripleChecker+Invalid, 105 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 76 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-16 18:00:23,754 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [45 Valid, 147 Invalid, 105 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 76 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-16 18:00:23,754 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2025-03-16 18:00:23,780 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 50. [2025-03-16 18:00:23,781 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 31 states have (on average 1.3870967741935485) internal successors, (43), 32 states have internal predecessors, (43), 15 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2025-03-16 18:00:23,782 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 72 transitions. [2025-03-16 18:00:23,782 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 72 transitions. Word has length 20 [2025-03-16 18:00:23,782 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:00:23,783 INFO L471 AbstractCegarLoop]: Abstraction has 50 states and 72 transitions. [2025-03-16 18:00:23,784 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 1.8888888888888888) internal successors, (17), 8 states have internal predecessors, (17), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-16 18:00:23,784 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 72 transitions. [2025-03-16 18:00:23,784 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2025-03-16 18:00:23,784 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:00:23,784 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:00:23,796 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-16 18:00:23,988 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:00:23,988 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:00:23,989 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:00:23,989 INFO L85 PathProgramCache]: Analyzing trace with hash 1009522679, now seen corresponding path program 1 times [2025-03-16 18:00:23,990 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:00:23,993 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [479535341] [2025-03-16 18:00:23,993 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:00:23,993 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:00:23,998 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-03-16 18:00:24,018 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-03-16 18:00:24,022 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:00:24,023 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:00:24,023 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [335347707] [2025-03-16 18:00:24,023 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:00:24,024 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:00:24,024 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:00:24,032 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-16 18:00:24,034 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-16 18:00:24,074 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-03-16 18:00:24,093 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-03-16 18:00:24,094 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:00:24,094 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:00:24,095 INFO L256 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 26 conjuncts are in the unsatisfiable core [2025-03-16 18:00:24,096 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:00:24,489 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-03-16 18:00:24,489 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:00:24,809 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-16 18:00:24,809 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:00:24,809 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [479535341] [2025-03-16 18:00:24,809 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:00:24,810 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [335347707] [2025-03-16 18:00:24,810 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [335347707] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:00:24,810 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:00:24,810 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 9] total 17 [2025-03-16 18:00:24,811 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [851886918] [2025-03-16 18:00:24,811 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:00:24,811 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2025-03-16 18:00:24,814 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:00:24,815 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2025-03-16 18:00:24,815 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=218, Unknown=0, NotChecked=0, Total=272 [2025-03-16 18:00:24,815 INFO L87 Difference]: Start difference. First operand 50 states and 72 transitions. Second operand has 17 states, 17 states have (on average 1.2941176470588236) internal successors, (22), 15 states have internal predecessors, (22), 4 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-16 18:00:26,074 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:00:26,074 INFO L93 Difference]: Finished difference Result 96 states and 143 transitions. [2025-03-16 18:00:26,074 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2025-03-16 18:00:26,075 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 1.2941176470588236) internal successors, (22), 15 states have internal predecessors, (22), 4 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 21 [2025-03-16 18:00:26,075 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:00:26,076 INFO L225 Difference]: With dead ends: 96 [2025-03-16 18:00:26,078 INFO L226 Difference]: Without dead ends: 94 [2025-03-16 18:00:26,082 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 50 GetRequests, 23 SyntacticMatches, 2 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 129 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=161, Invalid=541, Unknown=0, NotChecked=0, Total=702 [2025-03-16 18:00:26,082 INFO L435 NwaCegarLoop]: 25 mSDtfsCounter, 86 mSDsluCounter, 169 mSDsCounter, 0 mSdLazyCounter, 256 mSolverCounterSat, 76 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 86 SdHoareTripleChecker+Valid, 194 SdHoareTripleChecker+Invalid, 332 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 76 IncrementalHoareTripleChecker+Valid, 256 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2025-03-16 18:00:26,083 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [86 Valid, 194 Invalid, 332 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [76 Valid, 256 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2025-03-16 18:00:26,083 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 94 states. [2025-03-16 18:00:26,121 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 94 to 76. [2025-03-16 18:00:26,121 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 76 states, 48 states have (on average 1.3958333333333333) internal successors, (67), 49 states have internal predecessors, (67), 23 states have call successors, (23), 4 states have call predecessors, (23), 4 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2025-03-16 18:00:26,122 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 76 states to 76 states and 112 transitions. [2025-03-16 18:00:26,122 INFO L78 Accepts]: Start accepts. Automaton has 76 states and 112 transitions. Word has length 21 [2025-03-16 18:00:26,122 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:00:26,122 INFO L471 AbstractCegarLoop]: Abstraction has 76 states and 112 transitions. [2025-03-16 18:00:26,122 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 1.2941176470588236) internal successors, (22), 15 states have internal predecessors, (22), 4 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-16 18:00:26,123 INFO L276 IsEmpty]: Start isEmpty. Operand 76 states and 112 transitions. [2025-03-16 18:00:26,123 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2025-03-16 18:00:26,123 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:00:26,123 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:00:26,149 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2025-03-16 18:00:26,329 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:00:26,329 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:00:26,330 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:00:26,330 INFO L85 PathProgramCache]: Analyzing trace with hash -1565801332, now seen corresponding path program 1 times [2025-03-16 18:00:26,330 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:00:26,330 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [617232952] [2025-03-16 18:00:26,330 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:00:26,330 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:00:26,343 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 26 statements into 1 equivalence classes. [2025-03-16 18:00:26,363 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 26 of 26 statements. [2025-03-16 18:00:26,363 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:00:26,363 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:00:26,363 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1504334937] [2025-03-16 18:00:26,363 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:00:26,364 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:00:26,364 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:00:26,376 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-16 18:00:26,378 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-16 18:00:26,419 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 26 statements into 1 equivalence classes. [2025-03-16 18:00:26,433 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 26 of 26 statements. [2025-03-16 18:00:26,433 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:00:26,433 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:00:26,443 INFO L256 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 30 conjuncts are in the unsatisfiable core [2025-03-16 18:00:26,445 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:00:26,756 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 5 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-03-16 18:00:26,756 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:00:27,027 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-16 18:00:27,027 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:00:27,027 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [617232952] [2025-03-16 18:00:27,027 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:00:27,027 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1504334937] [2025-03-16 18:00:27,027 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1504334937] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:00:27,027 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:00:27,031 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9] total 16 [2025-03-16 18:00:27,031 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [374268737] [2025-03-16 18:00:27,031 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:00:27,031 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-03-16 18:00:27,031 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:00:27,031 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-03-16 18:00:27,032 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=198, Unknown=0, NotChecked=0, Total=240 [2025-03-16 18:00:27,032 INFO L87 Difference]: Start difference. First operand 76 states and 112 transitions. Second operand has 16 states, 16 states have (on average 1.5625) internal successors, (25), 14 states have internal predecessors, (25), 4 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 4 states have call predecessors, (6), 4 states have call successors, (6) [2025-03-16 18:00:28,728 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:00:28,729 INFO L93 Difference]: Finished difference Result 156 states and 240 transitions. [2025-03-16 18:00:28,729 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2025-03-16 18:00:28,729 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 1.5625) internal successors, (25), 14 states have internal predecessors, (25), 4 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 4 states have call predecessors, (6), 4 states have call successors, (6) Word has length 26 [2025-03-16 18:00:28,733 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:00:28,734 INFO L225 Difference]: With dead ends: 156 [2025-03-16 18:00:28,734 INFO L226 Difference]: Without dead ends: 154 [2025-03-16 18:00:28,737 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 34 SyntacticMatches, 2 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 252 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=274, Invalid=916, Unknown=0, NotChecked=0, Total=1190 [2025-03-16 18:00:28,737 INFO L435 NwaCegarLoop]: 21 mSDtfsCounter, 139 mSDsluCounter, 132 mSDsCounter, 0 mSdLazyCounter, 297 mSolverCounterSat, 107 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 139 SdHoareTripleChecker+Valid, 153 SdHoareTripleChecker+Invalid, 404 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 107 IncrementalHoareTripleChecker+Valid, 297 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2025-03-16 18:00:28,737 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [139 Valid, 153 Invalid, 404 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [107 Valid, 297 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2025-03-16 18:00:28,738 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 154 states. [2025-03-16 18:00:28,818 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 154 to 121. [2025-03-16 18:00:28,818 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 121 states, 79 states have (on average 1.4177215189873418) internal successors, (112), 80 states have internal predecessors, (112), 35 states have call successors, (35), 6 states have call predecessors, (35), 6 states have return successors, (34), 34 states have call predecessors, (34), 34 states have call successors, (34) [2025-03-16 18:00:28,819 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 121 states to 121 states and 181 transitions. [2025-03-16 18:00:28,819 INFO L78 Accepts]: Start accepts. Automaton has 121 states and 181 transitions. Word has length 26 [2025-03-16 18:00:28,819 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:00:28,819 INFO L471 AbstractCegarLoop]: Abstraction has 121 states and 181 transitions. [2025-03-16 18:00:28,819 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 1.5625) internal successors, (25), 14 states have internal predecessors, (25), 4 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 4 states have call predecessors, (6), 4 states have call successors, (6) [2025-03-16 18:00:28,820 INFO L276 IsEmpty]: Start isEmpty. Operand 121 states and 181 transitions. [2025-03-16 18:00:28,820 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2025-03-16 18:00:28,820 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:00:28,820 INFO L218 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:00:28,837 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2025-03-16 18:00:29,027 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:00:29,027 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:00:29,027 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:00:29,028 INFO L85 PathProgramCache]: Analyzing trace with hash -309678569, now seen corresponding path program 2 times [2025-03-16 18:00:29,028 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:00:29,028 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1171791715] [2025-03-16 18:00:29,028 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:00:29,028 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:00:29,038 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 27 statements into 2 equivalence classes. [2025-03-16 18:00:29,050 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 27 of 27 statements. [2025-03-16 18:00:29,050 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:00:29,057 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:00:29,164 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2025-03-16 18:00:29,164 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:00:29,164 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1171791715] [2025-03-16 18:00:29,164 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1171791715] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:00:29,164 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:00:29,164 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:00:29,165 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [888078452] [2025-03-16 18:00:29,165 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:00:29,165 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:00:29,165 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:00:29,165 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:00:29,165 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:00:29,165 INFO L87 Difference]: Start difference. First operand 121 states and 181 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2025-03-16 18:00:29,317 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:00:29,317 INFO L93 Difference]: Finished difference Result 174 states and 262 transitions. [2025-03-16 18:00:29,317 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-16 18:00:29,318 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 27 [2025-03-16 18:00:29,321 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:00:29,322 INFO L225 Difference]: With dead ends: 174 [2025-03-16 18:00:29,322 INFO L226 Difference]: Without dead ends: 96 [2025-03-16 18:00:29,323 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2025-03-16 18:00:29,323 INFO L435 NwaCegarLoop]: 31 mSDtfsCounter, 13 mSDsluCounter, 73 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 104 SdHoareTripleChecker+Invalid, 58 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:00:29,324 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 104 Invalid, 58 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:00:29,327 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 96 states. [2025-03-16 18:00:29,366 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 96 to 75. [2025-03-16 18:00:29,370 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 75 states, 45 states have (on average 1.288888888888889) internal successors, (58), 46 states have internal predecessors, (58), 23 states have call successors, (23), 6 states have call predecessors, (23), 6 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2025-03-16 18:00:29,372 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 103 transitions. [2025-03-16 18:00:29,373 INFO L78 Accepts]: Start accepts. Automaton has 75 states and 103 transitions. Word has length 27 [2025-03-16 18:00:29,373 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:00:29,373 INFO L471 AbstractCegarLoop]: Abstraction has 75 states and 103 transitions. [2025-03-16 18:00:29,373 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2025-03-16 18:00:29,373 INFO L276 IsEmpty]: Start isEmpty. Operand 75 states and 103 transitions. [2025-03-16 18:00:29,373 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2025-03-16 18:00:29,373 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:00:29,373 INFO L218 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:00:29,374 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2025-03-16 18:00:29,374 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:00:29,374 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:00:29,374 INFO L85 PathProgramCache]: Analyzing trace with hash -214133417, now seen corresponding path program 1 times [2025-03-16 18:00:29,374 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:00:29,379 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1407633925] [2025-03-16 18:00:29,379 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:00:29,379 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:00:29,399 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-16 18:00:29,414 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-16 18:00:29,414 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:00:29,414 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:00:29,422 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [282400531] [2025-03-16 18:00:29,422 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:00:29,422 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:00:29,422 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:00:29,430 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:00:29,438 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2025-03-16 18:00:29,472 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-16 18:00:29,484 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-16 18:00:29,485 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:00:29,485 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:00:29,486 INFO L256 TraceCheckSpWp]: Trace formula consists of 110 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-16 18:00:29,487 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:00:29,535 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2025-03-16 18:00:29,539 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-16 18:00:29,540 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:00:29,540 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1407633925] [2025-03-16 18:00:29,540 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:00:29,540 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [282400531] [2025-03-16 18:00:29,540 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [282400531] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:00:29,540 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:00:29,540 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:00:29,540 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [172065936] [2025-03-16 18:00:29,541 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:00:29,541 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:00:29,541 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:00:29,541 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:00:29,541 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:00:29,542 INFO L87 Difference]: Start difference. First operand 75 states and 103 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-16 18:00:29,702 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:00:29,702 INFO L93 Difference]: Finished difference Result 104 states and 145 transitions. [2025-03-16 18:00:29,707 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 18:00:29,707 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 31 [2025-03-16 18:00:29,707 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:00:29,708 INFO L225 Difference]: With dead ends: 104 [2025-03-16 18:00:29,708 INFO L226 Difference]: Without dead ends: 102 [2025-03-16 18:00:29,708 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 31 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2025-03-16 18:00:29,709 INFO L435 NwaCegarLoop]: 25 mSDtfsCounter, 6 mSDsluCounter, 63 mSDsCounter, 0 mSdLazyCounter, 43 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 88 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 43 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:00:29,709 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 88 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 43 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:00:29,709 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 102 states. [2025-03-16 18:00:29,757 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 102 to 98. [2025-03-16 18:00:29,758 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 98 states, 54 states have (on average 1.2962962962962963) internal successors, (70), 55 states have internal predecessors, (70), 35 states have call successors, (35), 8 states have call predecessors, (35), 8 states have return successors, (34), 34 states have call predecessors, (34), 34 states have call successors, (34) [2025-03-16 18:00:29,762 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 139 transitions. [2025-03-16 18:00:29,763 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 139 transitions. Word has length 31 [2025-03-16 18:00:29,763 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:00:29,763 INFO L471 AbstractCegarLoop]: Abstraction has 98 states and 139 transitions. [2025-03-16 18:00:29,767 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-16 18:00:29,767 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 139 transitions. [2025-03-16 18:00:29,768 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2025-03-16 18:00:29,768 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:00:29,768 INFO L218 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:00:29,780 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2025-03-16 18:00:29,969 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:00:29,969 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:00:29,969 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:00:29,969 INFO L85 PathProgramCache]: Analyzing trace with hash 1704179857, now seen corresponding path program 1 times [2025-03-16 18:00:29,969 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:00:29,969 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [512006511] [2025-03-16 18:00:29,969 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:00:29,970 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:00:29,978 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 33 statements into 1 equivalence classes. [2025-03-16 18:00:29,998 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 33 of 33 statements. [2025-03-16 18:00:29,998 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:00:29,998 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:00:29,999 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [440953768] [2025-03-16 18:00:29,999 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:00:29,999 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:00:29,999 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:00:30,005 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:00:30,010 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2025-03-16 18:00:30,066 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 33 statements into 1 equivalence classes. [2025-03-16 18:00:30,080 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 33 of 33 statements. [2025-03-16 18:00:30,080 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:00:30,080 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:00:30,081 INFO L256 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-16 18:00:30,082 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:00:30,145 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2025-03-16 18:00:30,146 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-16 18:00:30,146 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:00:30,146 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [512006511] [2025-03-16 18:00:30,146 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:00:30,146 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [440953768] [2025-03-16 18:00:30,146 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [440953768] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:00:30,146 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:00:30,146 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:00:30,146 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1495475517] [2025-03-16 18:00:30,146 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:00:30,146 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:00:30,146 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:00:30,147 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:00:30,147 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:00:30,147 INFO L87 Difference]: Start difference. First operand 98 states and 139 transitions. Second operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2025-03-16 18:00:30,304 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:00:30,304 INFO L93 Difference]: Finished difference Result 148 states and 228 transitions. [2025-03-16 18:00:30,305 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 18:00:30,305 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 33 [2025-03-16 18:00:30,305 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:00:30,312 INFO L225 Difference]: With dead ends: 148 [2025-03-16 18:00:30,312 INFO L226 Difference]: Without dead ends: 146 [2025-03-16 18:00:30,312 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 33 GetRequests, 29 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2025-03-16 18:00:30,312 INFO L435 NwaCegarLoop]: 28 mSDtfsCounter, 4 mSDsluCounter, 68 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 96 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:00:30,313 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 96 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:00:30,313 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 146 states. [2025-03-16 18:00:30,392 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 146 to 134. [2025-03-16 18:00:30,396 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 134 states, 57 states have (on average 1.280701754385965) internal successors, (73), 66 states have internal predecessors, (73), 67 states have call successors, (67), 9 states have call predecessors, (67), 9 states have return successors, (66), 58 states have call predecessors, (66), 66 states have call successors, (66) [2025-03-16 18:00:30,397 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 134 states to 134 states and 206 transitions. [2025-03-16 18:00:30,398 INFO L78 Accepts]: Start accepts. Automaton has 134 states and 206 transitions. Word has length 33 [2025-03-16 18:00:30,399 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:00:30,399 INFO L471 AbstractCegarLoop]: Abstraction has 134 states and 206 transitions. [2025-03-16 18:00:30,399 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2025-03-16 18:00:30,400 INFO L276 IsEmpty]: Start isEmpty. Operand 134 states and 206 transitions. [2025-03-16 18:00:30,405 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2025-03-16 18:00:30,405 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:00:30,405 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:00:30,417 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2025-03-16 18:00:30,607 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:00:30,607 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:00:30,608 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:00:30,608 INFO L85 PathProgramCache]: Analyzing trace with hash 16168489, now seen corresponding path program 1 times [2025-03-16 18:00:30,608 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:00:30,608 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1218070078] [2025-03-16 18:00:30,608 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:00:30,608 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:00:30,619 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 43 statements into 1 equivalence classes. [2025-03-16 18:00:30,638 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 43 of 43 statements. [2025-03-16 18:00:30,639 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:00:30,639 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:00:30,639 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [131894953] [2025-03-16 18:00:30,639 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:00:30,639 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:00:30,640 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:00:30,648 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:00:30,649 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2025-03-16 18:00:30,684 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 43 statements into 1 equivalence classes. [2025-03-16 18:00:30,711 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 43 of 43 statements. [2025-03-16 18:00:30,715 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:00:30,716 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:00:30,717 INFO L256 TraceCheckSpWp]: Trace formula consists of 130 conjuncts, 51 conjuncts are in the unsatisfiable core [2025-03-16 18:00:30,718 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:00:31,486 INFO L134 CoverageAnalysis]: Checked inductivity of 38 backedges. 8 proven. 5 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2025-03-16 18:00:31,489 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:00:32,007 INFO L134 CoverageAnalysis]: Checked inductivity of 38 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2025-03-16 18:00:32,007 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:00:32,007 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1218070078] [2025-03-16 18:00:32,007 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:00:32,007 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [131894953] [2025-03-16 18:00:32,007 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [131894953] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:00:32,007 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:00:32,007 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 23 [2025-03-16 18:00:32,007 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [977791309] [2025-03-16 18:00:32,007 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:00:32,013 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2025-03-16 18:00:32,013 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:00:32,013 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2025-03-16 18:00:32,013 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=77, Invalid=429, Unknown=0, NotChecked=0, Total=506 [2025-03-16 18:00:32,013 INFO L87 Difference]: Start difference. First operand 134 states and 206 transitions. Second operand has 23 states, 21 states have (on average 1.4761904761904763) internal successors, (31), 20 states have internal predecessors, (31), 6 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2025-03-16 18:00:34,201 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:00:34,202 INFO L93 Difference]: Finished difference Result 362 states and 580 transitions. [2025-03-16 18:00:34,202 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2025-03-16 18:00:34,202 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 21 states have (on average 1.4761904761904763) internal successors, (31), 20 states have internal predecessors, (31), 6 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 43 [2025-03-16 18:00:34,203 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:00:34,206 INFO L225 Difference]: With dead ends: 362 [2025-03-16 18:00:34,206 INFO L226 Difference]: Without dead ends: 276 [2025-03-16 18:00:34,210 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 107 GetRequests, 63 SyntacticMatches, 0 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 432 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=398, Invalid=1672, Unknown=0, NotChecked=0, Total=2070 [2025-03-16 18:00:34,210 INFO L435 NwaCegarLoop]: 19 mSDtfsCounter, 116 mSDsluCounter, 202 mSDsCounter, 0 mSdLazyCounter, 516 mSolverCounterSat, 127 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 124 SdHoareTripleChecker+Valid, 221 SdHoareTripleChecker+Invalid, 643 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 127 IncrementalHoareTripleChecker+Valid, 516 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2025-03-16 18:00:34,211 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [124 Valid, 221 Invalid, 643 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [127 Valid, 516 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2025-03-16 18:00:34,212 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 276 states. [2025-03-16 18:00:34,305 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 276 to 204. [2025-03-16 18:00:34,306 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 204 states, 100 states have (on average 1.31) internal successors, (131), 107 states have internal predecessors, (131), 91 states have call successors, (91), 12 states have call predecessors, (91), 12 states have return successors, (90), 84 states have call predecessors, (90), 90 states have call successors, (90) [2025-03-16 18:00:34,310 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 204 states to 204 states and 312 transitions. [2025-03-16 18:00:34,310 INFO L78 Accepts]: Start accepts. Automaton has 204 states and 312 transitions. Word has length 43 [2025-03-16 18:00:34,311 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:00:34,311 INFO L471 AbstractCegarLoop]: Abstraction has 204 states and 312 transitions. [2025-03-16 18:00:34,311 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 21 states have (on average 1.4761904761904763) internal successors, (31), 20 states have internal predecessors, (31), 6 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2025-03-16 18:00:34,311 INFO L276 IsEmpty]: Start isEmpty. Operand 204 states and 312 transitions. [2025-03-16 18:00:34,312 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2025-03-16 18:00:34,312 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:00:34,312 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:00:34,321 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2025-03-16 18:00:34,518 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2025-03-16 18:00:34,518 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:00:34,519 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:00:34,519 INFO L85 PathProgramCache]: Analyzing trace with hash 1270686876, now seen corresponding path program 1 times [2025-03-16 18:00:34,522 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:00:34,522 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1924491186] [2025-03-16 18:00:34,522 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:00:34,522 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:00:34,528 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 47 statements into 1 equivalence classes. [2025-03-16 18:00:34,551 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 47 of 47 statements. [2025-03-16 18:00:34,558 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:00:34,559 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:00:34,560 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [324550995] [2025-03-16 18:00:34,560 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:00:34,560 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:00:34,560 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:00:34,567 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:00:34,578 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2025-03-16 18:00:34,607 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 47 statements into 1 equivalence classes. [2025-03-16 18:00:34,628 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 47 of 47 statements. [2025-03-16 18:00:34,628 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:00:34,628 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:00:34,629 INFO L256 TraceCheckSpWp]: Trace formula consists of 156 conjuncts, 41 conjuncts are in the unsatisfiable core [2025-03-16 18:00:34,635 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:00:35,064 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 8 proven. 14 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2025-03-16 18:00:35,064 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:00:35,494 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 10 proven. 9 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2025-03-16 18:00:35,497 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:00:35,498 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1924491186] [2025-03-16 18:00:35,498 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:00:35,498 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [324550995] [2025-03-16 18:00:35,498 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [324550995] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:00:35,498 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:00:35,498 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 12] total 25 [2025-03-16 18:00:35,498 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1559581271] [2025-03-16 18:00:35,498 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:00:35,498 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2025-03-16 18:00:35,498 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:00:35,499 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2025-03-16 18:00:35,499 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=91, Invalid=509, Unknown=0, NotChecked=0, Total=600 [2025-03-16 18:00:35,499 INFO L87 Difference]: Start difference. First operand 204 states and 312 transitions. Second operand has 25 states, 25 states have (on average 1.56) internal successors, (39), 22 states have internal predecessors, (39), 6 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2025-03-16 18:00:38,743 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:00:38,744 INFO L93 Difference]: Finished difference Result 284 states and 440 transitions. [2025-03-16 18:00:38,745 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2025-03-16 18:00:38,745 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 25 states have (on average 1.56) internal successors, (39), 22 states have internal predecessors, (39), 6 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 47 [2025-03-16 18:00:38,746 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:00:38,747 INFO L225 Difference]: With dead ends: 284 [2025-03-16 18:00:38,747 INFO L226 Difference]: Without dead ends: 282 [2025-03-16 18:00:38,748 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 110 GetRequests, 69 SyntacticMatches, 0 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 337 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=341, Invalid=1465, Unknown=0, NotChecked=0, Total=1806 [2025-03-16 18:00:38,748 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 124 mSDsluCounter, 364 mSDsCounter, 0 mSdLazyCounter, 595 mSolverCounterSat, 157 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 124 SdHoareTripleChecker+Valid, 402 SdHoareTripleChecker+Invalid, 752 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 157 IncrementalHoareTripleChecker+Valid, 595 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.7s IncrementalHoareTripleChecker+Time [2025-03-16 18:00:38,753 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [124 Valid, 402 Invalid, 752 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [157 Valid, 595 Invalid, 0 Unknown, 0 Unchecked, 1.7s Time] [2025-03-16 18:00:38,757 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 282 states. [2025-03-16 18:00:38,952 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 282 to 237. [2025-03-16 18:00:38,957 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 237 states, 115 states have (on average 1.3043478260869565) internal successors, (150), 124 states have internal predecessors, (150), 107 states have call successors, (107), 14 states have call predecessors, (107), 14 states have return successors, (106), 98 states have call predecessors, (106), 106 states have call successors, (106) [2025-03-16 18:00:38,962 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 237 states to 237 states and 363 transitions. [2025-03-16 18:00:38,964 INFO L78 Accepts]: Start accepts. Automaton has 237 states and 363 transitions. Word has length 47 [2025-03-16 18:00:38,965 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:00:38,965 INFO L471 AbstractCegarLoop]: Abstraction has 237 states and 363 transitions. [2025-03-16 18:00:38,965 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 25 states have (on average 1.56) internal successors, (39), 22 states have internal predecessors, (39), 6 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2025-03-16 18:00:38,965 INFO L276 IsEmpty]: Start isEmpty. Operand 237 states and 363 transitions. [2025-03-16 18:00:38,966 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2025-03-16 18:00:38,968 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:00:38,968 INFO L218 NwaCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:00:38,980 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2025-03-16 18:00:39,168 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:00:39,169 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:00:39,169 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:00:39,169 INFO L85 PathProgramCache]: Analyzing trace with hash -136742532, now seen corresponding path program 1 times [2025-03-16 18:00:39,170 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:00:39,170 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1896380526] [2025-03-16 18:00:39,170 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:00:39,170 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:00:39,178 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 54 statements into 1 equivalence classes. [2025-03-16 18:00:39,197 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 54 of 54 statements. [2025-03-16 18:00:39,197 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:00:39,197 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:00:39,198 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1650982906] [2025-03-16 18:00:39,198 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:00:39,198 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:00:39,198 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:00:39,205 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:00:39,206 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2025-03-16 18:00:39,254 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 54 statements into 1 equivalence classes. [2025-03-16 18:00:39,270 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 54 of 54 statements. [2025-03-16 18:00:39,270 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:00:39,271 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:00:39,271 INFO L256 TraceCheckSpWp]: Trace formula consists of 142 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-16 18:00:39,273 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:00:39,363 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 14 proven. 4 refuted. 0 times theorem prover too weak. 88 trivial. 0 not checked. [2025-03-16 18:00:39,363 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:00:39,447 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 14 proven. 0 refuted. 0 times theorem prover too weak. 92 trivial. 0 not checked. [2025-03-16 18:00:39,448 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:00:39,448 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1896380526] [2025-03-16 18:00:39,448 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:00:39,448 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1650982906] [2025-03-16 18:00:39,448 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1650982906] provided 1 perfect and 1 imperfect interpolant sequences [2025-03-16 18:00:39,448 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:00:39,448 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2025-03-16 18:00:39,448 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [600322845] [2025-03-16 18:00:39,448 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:00:39,448 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:00:39,448 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:00:39,449 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:00:39,449 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2025-03-16 18:00:39,449 INFO L87 Difference]: Start difference. First operand 237 states and 363 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2025-03-16 18:00:39,687 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:00:39,687 INFO L93 Difference]: Finished difference Result 243 states and 368 transitions. [2025-03-16 18:00:39,688 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 18:00:39,688 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 54 [2025-03-16 18:00:39,689 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:00:39,694 INFO L225 Difference]: With dead ends: 243 [2025-03-16 18:00:39,694 INFO L226 Difference]: Without dead ends: 241 [2025-03-16 18:00:39,695 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 107 GetRequests, 99 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2025-03-16 18:00:39,695 INFO L435 NwaCegarLoop]: 28 mSDtfsCounter, 4 mSDsluCounter, 64 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 92 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 18:00:39,695 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 92 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 18:00:39,696 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 241 states. [2025-03-16 18:00:39,895 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 241 to 241. [2025-03-16 18:00:39,896 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 241 states, 118 states have (on average 1.2966101694915255) internal successors, (153), 127 states have internal predecessors, (153), 107 states have call successors, (107), 15 states have call predecessors, (107), 15 states have return successors, (106), 98 states have call predecessors, (106), 106 states have call successors, (106) [2025-03-16 18:00:39,897 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 241 states to 241 states and 366 transitions. [2025-03-16 18:00:39,903 INFO L78 Accepts]: Start accepts. Automaton has 241 states and 366 transitions. Word has length 54 [2025-03-16 18:00:39,904 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:00:39,904 INFO L471 AbstractCegarLoop]: Abstraction has 241 states and 366 transitions. [2025-03-16 18:00:39,904 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2025-03-16 18:00:39,904 INFO L276 IsEmpty]: Start isEmpty. Operand 241 states and 366 transitions. [2025-03-16 18:00:39,905 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2025-03-16 18:00:39,905 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:00:39,905 INFO L218 NwaCegarLoop]: trace histogram [6, 5, 5, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:00:39,919 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2025-03-16 18:00:40,108 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2025-03-16 18:00:40,108 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:00:40,109 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:00:40,109 INFO L85 PathProgramCache]: Analyzing trace with hash 963761927, now seen corresponding path program 2 times [2025-03-16 18:00:40,109 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:00:40,109 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [413531788] [2025-03-16 18:00:40,109 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:00:40,109 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:00:40,116 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 52 statements into 2 equivalence classes. [2025-03-16 18:00:40,142 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 52 of 52 statements. [2025-03-16 18:00:40,145 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:00:40,145 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:00:40,145 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1315909100] [2025-03-16 18:00:40,145 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:00:40,145 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:00:40,149 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:00:40,151 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:00:40,152 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2025-03-16 18:00:40,197 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 52 statements into 2 equivalence classes. [2025-03-16 18:00:40,229 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 52 of 52 statements. [2025-03-16 18:00:40,230 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:00:40,230 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:00:40,231 INFO L256 TraceCheckSpWp]: Trace formula consists of 165 conjuncts, 59 conjuncts are in the unsatisfiable core [2025-03-16 18:00:40,233 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:00:40,902 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 10 proven. 15 refuted. 0 times theorem prover too weak. 41 trivial. 0 not checked. [2025-03-16 18:00:40,902 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:00:41,353 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 12 proven. 10 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2025-03-16 18:00:41,354 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:00:41,354 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [413531788] [2025-03-16 18:00:41,354 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:00:41,354 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1315909100] [2025-03-16 18:00:41,354 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1315909100] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:00:41,354 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:00:41,354 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 13] total 27 [2025-03-16 18:00:41,354 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1438230434] [2025-03-16 18:00:41,354 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:00:41,354 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2025-03-16 18:00:41,354 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:00:41,355 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2025-03-16 18:00:41,355 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=97, Invalid=605, Unknown=0, NotChecked=0, Total=702 [2025-03-16 18:00:41,355 INFO L87 Difference]: Start difference. First operand 241 states and 366 transitions. Second operand has 27 states, 27 states have (on average 1.4444444444444444) internal successors, (39), 24 states have internal predecessors, (39), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 6 states have call predecessors, (14), 6 states have call successors, (14) [2025-03-16 18:00:44,597 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:00:44,597 INFO L93 Difference]: Finished difference Result 472 states and 736 transitions. [2025-03-16 18:00:44,597 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2025-03-16 18:00:44,598 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 27 states have (on average 1.4444444444444444) internal successors, (39), 24 states have internal predecessors, (39), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 6 states have call predecessors, (14), 6 states have call successors, (14) Word has length 52 [2025-03-16 18:00:44,598 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:00:44,600 INFO L225 Difference]: With dead ends: 472 [2025-03-16 18:00:44,600 INFO L226 Difference]: Without dead ends: 384 [2025-03-16 18:00:44,601 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 130 GetRequests, 77 SyntacticMatches, 0 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 610 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=575, Invalid=2395, Unknown=0, NotChecked=0, Total=2970 [2025-03-16 18:00:44,602 INFO L435 NwaCegarLoop]: 30 mSDtfsCounter, 144 mSDsluCounter, 302 mSDsCounter, 0 mSdLazyCounter, 732 mSolverCounterSat, 185 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 144 SdHoareTripleChecker+Valid, 332 SdHoareTripleChecker+Invalid, 917 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 185 IncrementalHoareTripleChecker+Valid, 732 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:00:44,603 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [144 Valid, 332 Invalid, 917 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [185 Valid, 732 Invalid, 0 Unknown, 0 Unchecked, 1.1s Time] [2025-03-16 18:00:44,603 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 384 states. [2025-03-16 18:00:44,765 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 384 to 338. [2025-03-16 18:00:44,766 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 338 states, 159 states have (on average 1.320754716981132) internal successors, (210), 172 states have internal predecessors, (210), 159 states have call successors, (159), 19 states have call predecessors, (159), 19 states have return successors, (158), 146 states have call predecessors, (158), 158 states have call successors, (158) [2025-03-16 18:00:44,768 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 338 states to 338 states and 527 transitions. [2025-03-16 18:00:44,768 INFO L78 Accepts]: Start accepts. Automaton has 338 states and 527 transitions. Word has length 52 [2025-03-16 18:00:44,768 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:00:44,768 INFO L471 AbstractCegarLoop]: Abstraction has 338 states and 527 transitions. [2025-03-16 18:00:44,769 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 27 states have (on average 1.4444444444444444) internal successors, (39), 24 states have internal predecessors, (39), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 6 states have call predecessors, (14), 6 states have call successors, (14) [2025-03-16 18:00:44,769 INFO L276 IsEmpty]: Start isEmpty. Operand 338 states and 527 transitions. [2025-03-16 18:00:44,769 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2025-03-16 18:00:44,769 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:00:44,769 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:00:44,775 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2025-03-16 18:00:44,974 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2025-03-16 18:00:44,974 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:00:44,974 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:00:44,974 INFO L85 PathProgramCache]: Analyzing trace with hash -2099826983, now seen corresponding path program 1 times [2025-03-16 18:00:44,974 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:00:44,974 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [707704637] [2025-03-16 18:00:44,974 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:00:44,974 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:00:44,978 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 67 statements into 1 equivalence classes. [2025-03-16 18:00:44,991 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 67 of 67 statements. [2025-03-16 18:00:44,991 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:00:44,991 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:00:44,992 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [708331392] [2025-03-16 18:00:44,992 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:00:44,992 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:00:44,992 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:00:44,994 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:00:44,995 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2025-03-16 18:00:45,016 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 67 statements into 1 equivalence classes. [2025-03-16 18:00:45,031 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 67 of 67 statements. [2025-03-16 18:00:45,031 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:00:45,031 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:00:45,032 INFO L256 TraceCheckSpWp]: Trace formula consists of 189 conjuncts, 77 conjuncts are in the unsatisfiable core [2025-03-16 18:00:45,034 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:00:45,650 INFO L134 CoverageAnalysis]: Checked inductivity of 144 backedges. 30 proven. 22 refuted. 0 times theorem prover too weak. 92 trivial. 0 not checked. [2025-03-16 18:00:45,650 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:00:46,253 INFO L134 CoverageAnalysis]: Checked inductivity of 144 backedges. 30 proven. 19 refuted. 0 times theorem prover too weak. 95 trivial. 0 not checked. [2025-03-16 18:00:46,253 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:00:46,253 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [707704637] [2025-03-16 18:00:46,253 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:00:46,253 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [708331392] [2025-03-16 18:00:46,253 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [708331392] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:00:46,253 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:00:46,253 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 16] total 33 [2025-03-16 18:00:46,253 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [559774827] [2025-03-16 18:00:46,253 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:00:46,254 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2025-03-16 18:00:46,254 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:00:46,254 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2025-03-16 18:00:46,254 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=151, Invalid=905, Unknown=0, NotChecked=0, Total=1056 [2025-03-16 18:00:46,254 INFO L87 Difference]: Start difference. First operand 338 states and 527 transitions. Second operand has 33 states, 30 states have (on average 1.4666666666666666) internal successors, (44), 31 states have internal predecessors, (44), 9 states have call successors, (21), 3 states have call predecessors, (21), 3 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) [2025-03-16 18:00:53,026 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:00:53,026 INFO L93 Difference]: Finished difference Result 507 states and 806 transitions. [2025-03-16 18:00:53,027 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 58 states. [2025-03-16 18:00:53,027 INFO L78 Accepts]: Start accepts. Automaton has has 33 states, 30 states have (on average 1.4666666666666666) internal successors, (44), 31 states have internal predecessors, (44), 9 states have call successors, (21), 3 states have call predecessors, (21), 3 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) Word has length 67 [2025-03-16 18:00:53,027 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:00:53,030 INFO L225 Difference]: With dead ends: 507 [2025-03-16 18:00:53,030 INFO L226 Difference]: Without dead ends: 499 [2025-03-16 18:00:53,031 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 178 GetRequests, 101 SyntacticMatches, 0 SemanticMatches, 77 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1590 ImplicationChecksByTransitivity, 4.0s TimeCoverageRelationStatistics Valid=1200, Invalid=4962, Unknown=0, NotChecked=0, Total=6162 [2025-03-16 18:00:53,031 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 151 mSDsluCounter, 523 mSDsCounter, 0 mSdLazyCounter, 1356 mSolverCounterSat, 233 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 151 SdHoareTripleChecker+Valid, 556 SdHoareTripleChecker+Invalid, 1589 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 233 IncrementalHoareTripleChecker+Valid, 1356 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.9s IncrementalHoareTripleChecker+Time [2025-03-16 18:00:53,032 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [151 Valid, 556 Invalid, 1589 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [233 Valid, 1356 Invalid, 0 Unknown, 0 Unchecked, 2.9s Time] [2025-03-16 18:00:53,032 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 499 states. [2025-03-16 18:00:53,365 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 499 to 461. [2025-03-16 18:00:53,366 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 461 states, 214 states have (on average 1.3457943925233644) internal successors, (288), 231 states have internal predecessors, (288), 223 states have call successors, (223), 23 states have call predecessors, (223), 23 states have return successors, (222), 206 states have call predecessors, (222), 222 states have call successors, (222) [2025-03-16 18:00:53,368 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 461 states to 461 states and 733 transitions. [2025-03-16 18:00:53,369 INFO L78 Accepts]: Start accepts. Automaton has 461 states and 733 transitions. Word has length 67 [2025-03-16 18:00:53,369 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:00:53,369 INFO L471 AbstractCegarLoop]: Abstraction has 461 states and 733 transitions. [2025-03-16 18:00:53,369 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 33 states, 30 states have (on average 1.4666666666666666) internal successors, (44), 31 states have internal predecessors, (44), 9 states have call successors, (21), 3 states have call predecessors, (21), 3 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) [2025-03-16 18:00:53,369 INFO L276 IsEmpty]: Start isEmpty. Operand 461 states and 733 transitions. [2025-03-16 18:00:53,370 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2025-03-16 18:00:53,370 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:00:53,370 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 8, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:00:53,384 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2025-03-16 18:00:53,570 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2025-03-16 18:00:53,571 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:00:53,571 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:00:53,571 INFO L85 PathProgramCache]: Analyzing trace with hash -857976004, now seen corresponding path program 3 times [2025-03-16 18:00:53,571 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:00:53,571 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [648094197] [2025-03-16 18:00:53,571 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 18:00:53,571 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:00:53,575 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 70 statements into 7 equivalence classes. [2025-03-16 18:00:53,597 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) and asserted 70 of 70 statements. [2025-03-16 18:00:53,597 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2025-03-16 18:00:53,597 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:00:53,598 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1316735580] [2025-03-16 18:00:53,599 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 18:00:53,599 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:00:53,599 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:00:53,603 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:00:53,604 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2025-03-16 18:00:53,627 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 70 statements into 7 equivalence classes. [2025-03-16 18:00:53,648 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 55 of 70 statements. [2025-03-16 18:00:53,648 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-03-16 18:00:53,648 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:00:53,649 INFO L256 TraceCheckSpWp]: Trace formula consists of 175 conjuncts, 56 conjuncts are in the unsatisfiable core [2025-03-16 18:00:53,650 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:00:54,052 INFO L134 CoverageAnalysis]: Checked inductivity of 154 backedges. 16 proven. 22 refuted. 0 times theorem prover too weak. 116 trivial. 0 not checked. [2025-03-16 18:00:54,052 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:00:54,628 INFO L134 CoverageAnalysis]: Checked inductivity of 154 backedges. 16 proven. 22 refuted. 0 times theorem prover too weak. 116 trivial. 0 not checked. [2025-03-16 18:00:54,628 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:00:54,628 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [648094197] [2025-03-16 18:00:54,628 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:00:54,628 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1316735580] [2025-03-16 18:00:54,628 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1316735580] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:00:54,628 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:00:54,628 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 16] total 27 [2025-03-16 18:00:54,628 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1759949211] [2025-03-16 18:00:54,628 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:00:54,628 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2025-03-16 18:00:54,628 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:00:54,629 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2025-03-16 18:00:54,629 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=136, Invalid=566, Unknown=0, NotChecked=0, Total=702 [2025-03-16 18:00:54,629 INFO L87 Difference]: Start difference. First operand 461 states and 733 transitions. Second operand has 27 states, 27 states have (on average 1.4814814814814814) internal successors, (40), 26 states have internal predecessors, (40), 7 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (18), 5 states have call predecessors, (18), 5 states have call successors, (18) [2025-03-16 18:01:05,002 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:01:05,002 INFO L93 Difference]: Finished difference Result 715 states and 1180 transitions. [2025-03-16 18:01:05,002 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 46 states. [2025-03-16 18:01:05,003 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 27 states have (on average 1.4814814814814814) internal successors, (40), 26 states have internal predecessors, (40), 7 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (18), 5 states have call predecessors, (18), 5 states have call successors, (18) Word has length 70 [2025-03-16 18:01:05,007 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:01:05,010 INFO L225 Difference]: With dead ends: 715 [2025-03-16 18:01:05,012 INFO L226 Difference]: Without dead ends: 713 [2025-03-16 18:01:05,017 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 179 GetRequests, 110 SyntacticMatches, 3 SemanticMatches, 66 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1231 ImplicationChecksByTransitivity, 6.0s TimeCoverageRelationStatistics Valid=959, Invalid=3597, Unknown=0, NotChecked=0, Total=4556 [2025-03-16 18:01:05,018 INFO L435 NwaCegarLoop]: 36 mSDtfsCounter, 211 mSDsluCounter, 409 mSDsCounter, 0 mSdLazyCounter, 778 mSolverCounterSat, 282 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 211 SdHoareTripleChecker+Valid, 445 SdHoareTripleChecker+Invalid, 1060 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 282 IncrementalHoareTripleChecker+Valid, 778 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.2s IncrementalHoareTripleChecker+Time [2025-03-16 18:01:05,018 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [211 Valid, 445 Invalid, 1060 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [282 Valid, 778 Invalid, 0 Unknown, 0 Unchecked, 4.2s Time] [2025-03-16 18:01:05,019 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 713 states. [2025-03-16 18:01:05,538 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 713 to 558. [2025-03-16 18:01:05,543 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 558 states, 258 states have (on average 1.3682170542635659) internal successors, (353), 277 states have internal predecessors, (353), 275 states have call successors, (275), 24 states have call predecessors, (275), 24 states have return successors, (274), 256 states have call predecessors, (274), 274 states have call successors, (274) [2025-03-16 18:01:05,547 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 558 states to 558 states and 902 transitions. [2025-03-16 18:01:05,552 INFO L78 Accepts]: Start accepts. Automaton has 558 states and 902 transitions. Word has length 70 [2025-03-16 18:01:05,553 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:01:05,553 INFO L471 AbstractCegarLoop]: Abstraction has 558 states and 902 transitions. [2025-03-16 18:01:05,553 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 27 states have (on average 1.4814814814814814) internal successors, (40), 26 states have internal predecessors, (40), 7 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (18), 5 states have call predecessors, (18), 5 states have call successors, (18) [2025-03-16 18:01:05,553 INFO L276 IsEmpty]: Start isEmpty. Operand 558 states and 902 transitions. [2025-03-16 18:01:05,554 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2025-03-16 18:01:05,554 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:01:05,555 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 8, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:01:05,575 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2025-03-16 18:01:05,755 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2025-03-16 18:01:05,756 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:01:05,756 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:01:05,756 INFO L85 PathProgramCache]: Analyzing trace with hash -23883137, now seen corresponding path program 2 times [2025-03-16 18:01:05,757 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:01:05,757 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1979012099] [2025-03-16 18:01:05,757 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:01:05,757 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:01:05,761 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 72 statements into 2 equivalence classes. [2025-03-16 18:01:05,785 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 72 of 72 statements. [2025-03-16 18:01:05,785 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:01:05,785 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:01:06,065 INFO L134 CoverageAnalysis]: Checked inductivity of 157 backedges. 28 proven. 11 refuted. 0 times theorem prover too weak. 118 trivial. 0 not checked. [2025-03-16 18:01:06,065 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:01:06,066 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1979012099] [2025-03-16 18:01:06,066 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1979012099] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:01:06,066 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [808624382] [2025-03-16 18:01:06,066 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:01:06,066 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:01:06,066 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:01:06,068 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:01:06,070 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2025-03-16 18:01:06,096 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 72 statements into 2 equivalence classes. [2025-03-16 18:01:06,113 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 72 of 72 statements. [2025-03-16 18:01:06,113 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:01:06,113 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:01:06,115 INFO L256 TraceCheckSpWp]: Trace formula consists of 212 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-03-16 18:01:06,117 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:01:06,189 INFO L134 CoverageAnalysis]: Checked inductivity of 157 backedges. 28 proven. 11 refuted. 0 times theorem prover too weak. 118 trivial. 0 not checked. [2025-03-16 18:01:06,189 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:01:06,306 INFO L134 CoverageAnalysis]: Checked inductivity of 157 backedges. 28 proven. 11 refuted. 0 times theorem prover too weak. 118 trivial. 0 not checked. [2025-03-16 18:01:06,307 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [808624382] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:01:06,307 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:01:06,307 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10, 10] total 13 [2025-03-16 18:01:06,310 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [158098526] [2025-03-16 18:01:06,311 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:01:06,311 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2025-03-16 18:01:06,311 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:01:06,311 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2025-03-16 18:01:06,311 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=129, Unknown=0, NotChecked=0, Total=156 [2025-03-16 18:01:06,311 INFO L87 Difference]: Start difference. First operand 558 states and 902 transitions. Second operand has 13 states, 13 states have (on average 2.4615384615384617) internal successors, (32), 13 states have internal predecessors, (32), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2025-03-16 18:01:07,504 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:01:07,504 INFO L93 Difference]: Finished difference Result 974 states and 1570 transitions. [2025-03-16 18:01:07,505 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2025-03-16 18:01:07,505 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.4615384615384617) internal successors, (32), 13 states have internal predecessors, (32), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) Word has length 72 [2025-03-16 18:01:07,505 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:01:07,514 INFO L225 Difference]: With dead ends: 974 [2025-03-16 18:01:07,514 INFO L226 Difference]: Without dead ends: 592 [2025-03-16 18:01:07,516 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 177 GetRequests, 140 SyntacticMatches, 8 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 164 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=214, Invalid=716, Unknown=0, NotChecked=0, Total=930 [2025-03-16 18:01:07,521 INFO L435 NwaCegarLoop]: 40 mSDtfsCounter, 54 mSDsluCounter, 236 mSDsCounter, 0 mSdLazyCounter, 291 mSolverCounterSat, 68 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 58 SdHoareTripleChecker+Valid, 276 SdHoareTripleChecker+Invalid, 359 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 68 IncrementalHoareTripleChecker+Valid, 291 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-03-16 18:01:07,521 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [58 Valid, 276 Invalid, 359 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [68 Valid, 291 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-03-16 18:01:07,522 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 592 states. [2025-03-16 18:01:07,934 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 592 to 440. [2025-03-16 18:01:07,937 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 440 states, 221 states have (on average 1.3257918552036199) internal successors, (293), 222 states have internal predecessors, (293), 195 states have call successors, (195), 23 states have call predecessors, (195), 23 states have return successors, (194), 194 states have call predecessors, (194), 194 states have call successors, (194) [2025-03-16 18:01:07,947 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 440 states to 440 states and 682 transitions. [2025-03-16 18:01:07,948 INFO L78 Accepts]: Start accepts. Automaton has 440 states and 682 transitions. Word has length 72 [2025-03-16 18:01:07,949 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:01:07,949 INFO L471 AbstractCegarLoop]: Abstraction has 440 states and 682 transitions. [2025-03-16 18:01:07,950 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.4615384615384617) internal successors, (32), 13 states have internal predecessors, (32), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2025-03-16 18:01:07,950 INFO L276 IsEmpty]: Start isEmpty. Operand 440 states and 682 transitions. [2025-03-16 18:01:07,953 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2025-03-16 18:01:07,958 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:01:07,959 INFO L218 NwaCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:01:07,973 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2025-03-16 18:01:08,159 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:01:08,160 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:01:08,160 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:01:08,160 INFO L85 PathProgramCache]: Analyzing trace with hash 986807614, now seen corresponding path program 2 times [2025-03-16 18:01:08,160 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:01:08,160 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1934481335] [2025-03-16 18:01:08,160 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:01:08,160 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:01:08,166 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 87 statements into 2 equivalence classes. [2025-03-16 18:01:08,180 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 87 of 87 statements. [2025-03-16 18:01:08,183 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:01:08,184 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:01:08,185 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1224704643] [2025-03-16 18:01:08,185 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:01:08,185 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:01:08,185 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:01:08,186 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:01:08,187 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2025-03-16 18:01:08,226 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 87 statements into 2 equivalence classes. [2025-03-16 18:01:08,246 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 87 of 87 statements. [2025-03-16 18:01:08,246 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:01:08,247 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:01:08,249 INFO L256 TraceCheckSpWp]: Trace formula consists of 217 conjuncts, 55 conjuncts are in the unsatisfiable core [2025-03-16 18:01:08,252 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:01:08,861 INFO L134 CoverageAnalysis]: Checked inductivity of 312 backedges. 24 proven. 20 refuted. 0 times theorem prover too weak. 268 trivial. 0 not checked. [2025-03-16 18:01:08,862 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:01:09,357 INFO L134 CoverageAnalysis]: Checked inductivity of 312 backedges. 24 proven. 20 refuted. 0 times theorem prover too weak. 268 trivial. 0 not checked. [2025-03-16 18:01:09,357 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:01:09,357 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1934481335] [2025-03-16 18:01:09,357 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:01:09,357 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1224704643] [2025-03-16 18:01:09,357 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1224704643] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:01:09,357 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:01:09,358 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 24 [2025-03-16 18:01:09,358 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1638255553] [2025-03-16 18:01:09,358 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:01:09,358 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2025-03-16 18:01:09,358 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:01:09,359 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2025-03-16 18:01:09,360 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=101, Invalid=451, Unknown=0, NotChecked=0, Total=552 [2025-03-16 18:01:09,361 INFO L87 Difference]: Start difference. First operand 440 states and 682 transitions. Second operand has 24 states, 22 states have (on average 1.5454545454545454) internal successors, (34), 23 states have internal predecessors, (34), 9 states have call successors, (28), 2 states have call predecessors, (28), 1 states have return successors, (26), 7 states have call predecessors, (26), 7 states have call successors, (26) [2025-03-16 18:01:17,830 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:01:17,831 INFO L93 Difference]: Finished difference Result 775 states and 1199 transitions. [2025-03-16 18:01:17,831 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 63 states. [2025-03-16 18:01:17,831 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 22 states have (on average 1.5454545454545454) internal successors, (34), 23 states have internal predecessors, (34), 9 states have call successors, (28), 2 states have call predecessors, (28), 1 states have return successors, (26), 7 states have call predecessors, (26), 7 states have call successors, (26) Word has length 87 [2025-03-16 18:01:17,835 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:01:17,842 INFO L225 Difference]: With dead ends: 775 [2025-03-16 18:01:17,842 INFO L226 Difference]: Without dead ends: 622 [2025-03-16 18:01:17,846 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 227 GetRequests, 148 SyntacticMatches, 2 SemanticMatches, 77 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1719 ImplicationChecksByTransitivity, 6.1s TimeCoverageRelationStatistics Valid=1157, Invalid=5005, Unknown=0, NotChecked=0, Total=6162 [2025-03-16 18:01:17,847 INFO L435 NwaCegarLoop]: 31 mSDtfsCounter, 178 mSDsluCounter, 315 mSDsCounter, 0 mSdLazyCounter, 714 mSolverCounterSat, 250 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 190 SdHoareTripleChecker+Valid, 346 SdHoareTripleChecker+Invalid, 964 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 250 IncrementalHoareTripleChecker+Valid, 714 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:01:17,847 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [190 Valid, 346 Invalid, 964 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [250 Valid, 714 Invalid, 0 Unknown, 0 Unchecked, 2.1s Time] [2025-03-16 18:01:17,850 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 622 states. [2025-03-16 18:01:18,468 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 622 to 537. [2025-03-16 18:01:18,469 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 537 states, 262 states have (on average 1.3358778625954197) internal successors, (350), 263 states have internal predecessors, (350), 247 states have call successors, (247), 27 states have call predecessors, (247), 27 states have return successors, (246), 246 states have call predecessors, (246), 246 states have call successors, (246) [2025-03-16 18:01:18,478 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 537 states to 537 states and 843 transitions. [2025-03-16 18:01:18,479 INFO L78 Accepts]: Start accepts. Automaton has 537 states and 843 transitions. Word has length 87 [2025-03-16 18:01:18,481 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:01:18,481 INFO L471 AbstractCegarLoop]: Abstraction has 537 states and 843 transitions. [2025-03-16 18:01:18,481 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 22 states have (on average 1.5454545454545454) internal successors, (34), 23 states have internal predecessors, (34), 9 states have call successors, (28), 2 states have call predecessors, (28), 1 states have return successors, (26), 7 states have call predecessors, (26), 7 states have call successors, (26) [2025-03-16 18:01:18,481 INFO L276 IsEmpty]: Start isEmpty. Operand 537 states and 843 transitions. [2025-03-16 18:01:18,486 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 95 [2025-03-16 18:01:18,486 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:01:18,486 INFO L218 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:01:18,497 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2025-03-16 18:01:18,687 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2025-03-16 18:01:18,687 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:01:18,689 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:01:18,689 INFO L85 PathProgramCache]: Analyzing trace with hash 1506194594, now seen corresponding path program 1 times [2025-03-16 18:01:18,689 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:01:18,689 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [808174267] [2025-03-16 18:01:18,689 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:01:18,689 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:01:18,697 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 94 statements into 1 equivalence classes. [2025-03-16 18:01:18,721 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 94 of 94 statements. [2025-03-16 18:01:18,722 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:01:18,722 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:01:18,723 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1614026878] [2025-03-16 18:01:18,723 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:01:18,723 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:01:18,723 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:01:18,730 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:01:18,731 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2025-03-16 18:01:18,759 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 94 statements into 1 equivalence classes. [2025-03-16 18:01:18,783 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 94 of 94 statements. [2025-03-16 18:01:18,784 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:01:18,784 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:01:18,785 INFO L256 TraceCheckSpWp]: Trace formula consists of 261 conjuncts, 84 conjuncts are in the unsatisfiable core [2025-03-16 18:01:18,787 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:01:21,286 INFO L134 CoverageAnalysis]: Checked inductivity of 335 backedges. 49 proven. 81 refuted. 0 times theorem prover too weak. 205 trivial. 0 not checked. [2025-03-16 18:01:21,286 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:01:21,660 INFO L134 CoverageAnalysis]: Checked inductivity of 335 backedges. 73 proven. 8 refuted. 0 times theorem prover too weak. 254 trivial. 0 not checked. [2025-03-16 18:01:21,663 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:01:21,664 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [808174267] [2025-03-16 18:01:21,664 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:01:21,664 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1614026878] [2025-03-16 18:01:21,664 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1614026878] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:01:21,664 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:01:21,664 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [27, 10] total 34 [2025-03-16 18:01:21,664 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1905083691] [2025-03-16 18:01:21,664 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:01:21,664 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 34 states [2025-03-16 18:01:21,664 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:01:21,665 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2025-03-16 18:01:21,665 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=140, Invalid=982, Unknown=0, NotChecked=0, Total=1122 [2025-03-16 18:01:21,665 INFO L87 Difference]: Start difference. First operand 537 states and 843 transitions. Second operand has 34 states, 32 states have (on average 1.65625) internal successors, (53), 31 states have internal predecessors, (53), 10 states have call successors, (23), 3 states have call predecessors, (23), 3 states have return successors, (23), 8 states have call predecessors, (23), 8 states have call successors, (23) [2025-03-16 18:01:31,559 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:01:31,559 INFO L93 Difference]: Finished difference Result 636 states and 997 transitions. [2025-03-16 18:01:31,560 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2025-03-16 18:01:31,560 INFO L78 Accepts]: Start accepts. Automaton has has 34 states, 32 states have (on average 1.65625) internal successors, (53), 31 states have internal predecessors, (53), 10 states have call successors, (23), 3 states have call predecessors, (23), 3 states have return successors, (23), 8 states have call predecessors, (23), 8 states have call successors, (23) Word has length 94 [2025-03-16 18:01:31,560 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:01:31,564 INFO L225 Difference]: With dead ends: 636 [2025-03-16 18:01:31,564 INFO L226 Difference]: Without dead ends: 634 [2025-03-16 18:01:31,566 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 218 GetRequests, 155 SyntacticMatches, 0 SemanticMatches, 63 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 975 ImplicationChecksByTransitivity, 6.2s TimeCoverageRelationStatistics Valid=600, Invalid=3560, Unknown=0, NotChecked=0, Total=4160 [2025-03-16 18:01:31,566 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 114 mSDsluCounter, 673 mSDsCounter, 0 mSdLazyCounter, 1643 mSolverCounterSat, 134 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 114 SdHoareTripleChecker+Valid, 711 SdHoareTripleChecker+Invalid, 1777 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 134 IncrementalHoareTripleChecker+Valid, 1643 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.2s IncrementalHoareTripleChecker+Time [2025-03-16 18:01:31,566 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [114 Valid, 711 Invalid, 1777 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [134 Valid, 1643 Invalid, 0 Unknown, 0 Unchecked, 4.2s Time] [2025-03-16 18:01:31,567 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 634 states. [2025-03-16 18:01:32,114 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 634 to 567. [2025-03-16 18:01:32,115 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 567 states, 274 states have (on average 1.3394160583941606) internal successors, (367), 275 states have internal predecessors, (367), 263 states have call successors, (263), 29 states have call predecessors, (263), 29 states have return successors, (262), 262 states have call predecessors, (262), 262 states have call successors, (262) [2025-03-16 18:01:32,117 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 567 states to 567 states and 892 transitions. [2025-03-16 18:01:32,118 INFO L78 Accepts]: Start accepts. Automaton has 567 states and 892 transitions. Word has length 94 [2025-03-16 18:01:32,118 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:01:32,118 INFO L471 AbstractCegarLoop]: Abstraction has 567 states and 892 transitions. [2025-03-16 18:01:32,118 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 34 states, 32 states have (on average 1.65625) internal successors, (53), 31 states have internal predecessors, (53), 10 states have call successors, (23), 3 states have call predecessors, (23), 3 states have return successors, (23), 8 states have call predecessors, (23), 8 states have call successors, (23) [2025-03-16 18:01:32,118 INFO L276 IsEmpty]: Start isEmpty. Operand 567 states and 892 transitions. [2025-03-16 18:01:32,119 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2025-03-16 18:01:32,119 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:01:32,119 INFO L218 NwaCegarLoop]: trace histogram [14, 13, 13, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:01:32,125 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2025-03-16 18:01:32,319 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2025-03-16 18:01:32,320 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:01:32,320 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:01:32,320 INFO L85 PathProgramCache]: Analyzing trace with hash 418647356, now seen corresponding path program 2 times [2025-03-16 18:01:32,320 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:01:32,320 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1261266113] [2025-03-16 18:01:32,320 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:01:32,320 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:01:32,323 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 96 statements into 2 equivalence classes. [2025-03-16 18:01:32,335 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 96 of 96 statements. [2025-03-16 18:01:32,336 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:01:32,336 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:01:32,337 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1689163385] [2025-03-16 18:01:32,337 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:01:32,337 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:01:32,337 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:01:32,339 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:01:32,341 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2025-03-16 18:01:32,364 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 96 statements into 2 equivalence classes. [2025-03-16 18:01:32,393 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 96 of 96 statements. [2025-03-16 18:01:32,393 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:01:32,394 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:01:32,395 INFO L256 TraceCheckSpWp]: Trace formula consists of 252 conjuncts, 63 conjuncts are in the unsatisfiable core [2025-03-16 18:01:32,397 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:01:33,170 INFO L134 CoverageAnalysis]: Checked inductivity of 378 backedges. 52 proven. 46 refuted. 0 times theorem prover too weak. 280 trivial. 0 not checked. [2025-03-16 18:01:33,170 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:01:34,676 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:01:34,677 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1261266113] [2025-03-16 18:01:34,677 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:01:34,677 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1689163385] [2025-03-16 18:01:34,677 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1689163385] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:01:34,677 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:01:34,677 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19] total 19 [2025-03-16 18:01:34,677 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [22171420] [2025-03-16 18:01:34,677 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 18:01:34,678 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2025-03-16 18:01:34,678 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:01:34,678 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2025-03-16 18:01:34,678 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=141, Invalid=789, Unknown=0, NotChecked=0, Total=930 [2025-03-16 18:01:34,678 INFO L87 Difference]: Start difference. First operand 567 states and 892 transitions. Second operand has 19 states, 18 states have (on average 1.6111111111111112) internal successors, (29), 18 states have internal predecessors, (29), 6 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 6 states have call predecessors, (15), 6 states have call successors, (15) [2025-03-16 18:01:36,307 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:01:36,307 INFO L93 Difference]: Finished difference Result 640 states and 991 transitions. [2025-03-16 18:01:36,307 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2025-03-16 18:01:36,308 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 18 states have (on average 1.6111111111111112) internal successors, (29), 18 states have internal predecessors, (29), 6 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 6 states have call predecessors, (15), 6 states have call successors, (15) Word has length 96 [2025-03-16 18:01:36,308 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:01:36,316 INFO L225 Difference]: With dead ends: 640 [2025-03-16 18:01:36,317 INFO L226 Difference]: Without dead ends: 638 [2025-03-16 18:01:36,317 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 169 GetRequests, 127 SyntacticMatches, 2 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 300 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=269, Invalid=1453, Unknown=0, NotChecked=0, Total=1722 [2025-03-16 18:01:36,321 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 56 mSDsluCounter, 430 mSDsCounter, 0 mSdLazyCounter, 837 mSolverCounterSat, 68 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 67 SdHoareTripleChecker+Valid, 468 SdHoareTripleChecker+Invalid, 905 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 68 IncrementalHoareTripleChecker+Valid, 837 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2025-03-16 18:01:36,322 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [67 Valid, 468 Invalid, 905 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [68 Valid, 837 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2025-03-16 18:01:36,323 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 638 states. [2025-03-16 18:01:36,993 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 638 to 620. [2025-03-16 18:01:36,994 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 620 states, 298 states have (on average 1.3355704697986577) internal successors, (398), 299 states have internal predecessors, (398), 287 states have call successors, (287), 34 states have call predecessors, (287), 34 states have return successors, (286), 286 states have call predecessors, (286), 286 states have call successors, (286) [2025-03-16 18:01:36,996 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 620 states to 620 states and 971 transitions. [2025-03-16 18:01:36,997 INFO L78 Accepts]: Start accepts. Automaton has 620 states and 971 transitions. Word has length 96 [2025-03-16 18:01:37,001 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:01:37,001 INFO L471 AbstractCegarLoop]: Abstraction has 620 states and 971 transitions. [2025-03-16 18:01:37,001 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 18 states have (on average 1.6111111111111112) internal successors, (29), 18 states have internal predecessors, (29), 6 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 6 states have call predecessors, (15), 6 states have call successors, (15) [2025-03-16 18:01:37,001 INFO L276 IsEmpty]: Start isEmpty. Operand 620 states and 971 transitions. [2025-03-16 18:01:37,002 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 100 [2025-03-16 18:01:37,002 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:01:37,002 INFO L218 NwaCegarLoop]: trace histogram [14, 13, 13, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:01:37,012 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Ended with exit code 0 [2025-03-16 18:01:37,202 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:01:37,203 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:01:37,204 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:01:37,204 INFO L85 PathProgramCache]: Analyzing trace with hash 1293900481, now seen corresponding path program 3 times [2025-03-16 18:01:37,204 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:01:37,204 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1594986200] [2025-03-16 18:01:37,204 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 18:01:37,204 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:01:37,208 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 99 statements into 8 equivalence classes. [2025-03-16 18:01:37,275 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 8 check-sat command(s) and asserted 99 of 99 statements. [2025-03-16 18:01:37,279 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 8 check-sat command(s) [2025-03-16 18:01:37,280 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:01:37,281 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1575849462] [2025-03-16 18:01:37,281 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 18:01:37,281 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:01:37,281 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:01:37,287 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:01:37,289 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2025-03-16 18:01:37,331 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 99 statements into 8 equivalence classes. [2025-03-16 18:01:37,382 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) and asserted 51 of 99 statements. [2025-03-16 18:01:37,383 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2025-03-16 18:01:37,383 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:01:37,384 INFO L256 TraceCheckSpWp]: Trace formula consists of 179 conjuncts, 81 conjuncts are in the unsatisfiable core [2025-03-16 18:01:37,386 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:01:38,532 INFO L134 CoverageAnalysis]: Checked inductivity of 388 backedges. 61 proven. 46 refuted. 0 times theorem prover too weak. 281 trivial. 0 not checked. [2025-03-16 18:01:38,535 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:01:41,696 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:01:41,696 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1594986200] [2025-03-16 18:01:41,697 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:01:41,697 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1575849462] [2025-03-16 18:01:41,697 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1575849462] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:01:41,697 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:01:41,697 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2025-03-16 18:01:41,697 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1352032362] [2025-03-16 18:01:41,697 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 18:01:41,697 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2025-03-16 18:01:41,697 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:01:41,698 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-03-16 18:01:41,698 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=146, Invalid=976, Unknown=0, NotChecked=0, Total=1122 [2025-03-16 18:01:41,699 INFO L87 Difference]: Start difference. First operand 620 states and 971 transitions. Second operand has 21 states, 20 states have (on average 1.6) internal successors, (32), 19 states have internal predecessors, (32), 6 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 5 states have call predecessors, (15), 5 states have call successors, (15) [2025-03-16 18:01:44,271 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:01:44,272 INFO L93 Difference]: Finished difference Result 763 states and 1188 transitions. [2025-03-16 18:01:44,272 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2025-03-16 18:01:44,272 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 20 states have (on average 1.6) internal successors, (32), 19 states have internal predecessors, (32), 6 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 5 states have call predecessors, (15), 5 states have call successors, (15) Word has length 99 [2025-03-16 18:01:44,272 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:01:44,288 INFO L225 Difference]: With dead ends: 763 [2025-03-16 18:01:44,288 INFO L226 Difference]: Without dead ends: 761 [2025-03-16 18:01:44,289 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 170 GetRequests, 129 SyntacticMatches, 0 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 450 ImplicationChecksByTransitivity, 3.5s TimeCoverageRelationStatistics Valid=241, Invalid=1565, Unknown=0, NotChecked=0, Total=1806 [2025-03-16 18:01:44,289 INFO L435 NwaCegarLoop]: 43 mSDtfsCounter, 68 mSDsluCounter, 544 mSDsCounter, 0 mSdLazyCounter, 1117 mSolverCounterSat, 58 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 81 SdHoareTripleChecker+Valid, 587 SdHoareTripleChecker+Invalid, 1175 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 58 IncrementalHoareTripleChecker+Valid, 1117 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.3s IncrementalHoareTripleChecker+Time [2025-03-16 18:01:44,289 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [81 Valid, 587 Invalid, 1175 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [58 Valid, 1117 Invalid, 0 Unknown, 0 Unchecked, 1.3s Time] [2025-03-16 18:01:44,290 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 761 states. [2025-03-16 18:01:45,143 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 761 to 740. [2025-03-16 18:01:45,147 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 740 states, 352 states have (on average 1.3409090909090908) internal successors, (472), 353 states have internal predecessors, (472), 347 states have call successors, (347), 40 states have call predecessors, (347), 40 states have return successors, (346), 346 states have call predecessors, (346), 346 states have call successors, (346) [2025-03-16 18:01:45,150 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 740 states to 740 states and 1165 transitions. [2025-03-16 18:01:45,155 INFO L78 Accepts]: Start accepts. Automaton has 740 states and 1165 transitions. Word has length 99 [2025-03-16 18:01:45,155 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:01:45,155 INFO L471 AbstractCegarLoop]: Abstraction has 740 states and 1165 transitions. [2025-03-16 18:01:45,155 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 20 states have (on average 1.6) internal successors, (32), 19 states have internal predecessors, (32), 6 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 5 states have call predecessors, (15), 5 states have call successors, (15) [2025-03-16 18:01:45,155 INFO L276 IsEmpty]: Start isEmpty. Operand 740 states and 1165 transitions. [2025-03-16 18:01:45,162 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 112 [2025-03-16 18:01:45,162 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:01:45,162 INFO L218 NwaCegarLoop]: trace histogram [17, 16, 16, 4, 4, 4, 4, 4, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:01:45,173 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2025-03-16 18:01:45,362 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:01:45,362 INFO L396 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:01:45,363 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:01:45,363 INFO L85 PathProgramCache]: Analyzing trace with hash -418043900, now seen corresponding path program 3 times [2025-03-16 18:01:45,363 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:01:45,363 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [220169550] [2025-03-16 18:01:45,363 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 18:01:45,363 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:01:45,370 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 111 statements into 12 equivalence classes. [2025-03-16 18:01:45,401 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 12 check-sat command(s) and asserted 111 of 111 statements. [2025-03-16 18:01:45,401 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 12 check-sat command(s) [2025-03-16 18:01:45,401 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:01:45,402 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1693662090] [2025-03-16 18:01:45,402 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 18:01:45,402 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:01:45,402 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:01:45,405 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:01:45,406 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2025-03-16 18:01:45,439 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 111 statements into 12 equivalence classes. [2025-03-16 18:01:45,557 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 59 of 111 statements. [2025-03-16 18:01:45,557 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-03-16 18:01:45,557 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:01:45,559 INFO L256 TraceCheckSpWp]: Trace formula consists of 162 conjuncts, 75 conjuncts are in the unsatisfiable core [2025-03-16 18:01:45,561 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:01:46,328 INFO L134 CoverageAnalysis]: Checked inductivity of 557 backedges. 200 proven. 44 refuted. 0 times theorem prover too weak. 313 trivial. 0 not checked. [2025-03-16 18:01:46,328 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:01:46,860 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:01:46,860 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [220169550] [2025-03-16 18:01:46,860 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:01:46,860 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1693662090] [2025-03-16 18:01:46,860 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1693662090] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:01:46,860 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:01:46,860 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23] total 23 [2025-03-16 18:01:46,860 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1727591281] [2025-03-16 18:01:46,860 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 18:01:46,860 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2025-03-16 18:01:46,860 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:01:46,861 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2025-03-16 18:01:46,861 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=123, Invalid=869, Unknown=0, NotChecked=0, Total=992 [2025-03-16 18:01:46,861 INFO L87 Difference]: Start difference. First operand 740 states and 1165 transitions. Second operand has 23 states, 17 states have (on average 1.8823529411764706) internal successors, (32), 17 states have internal predecessors, (32), 8 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (12), 8 states have call predecessors, (12), 7 states have call successors, (12) [2025-03-16 18:01:52,590 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:01:52,590 INFO L93 Difference]: Finished difference Result 1063 states and 1666 transitions. [2025-03-16 18:01:52,591 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 46 states. [2025-03-16 18:01:52,591 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 17 states have (on average 1.8823529411764706) internal successors, (32), 17 states have internal predecessors, (32), 8 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (12), 8 states have call predecessors, (12), 7 states have call successors, (12) Word has length 111 [2025-03-16 18:01:52,591 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:01:52,596 INFO L225 Difference]: With dead ends: 1063 [2025-03-16 18:01:52,596 INFO L226 Difference]: Without dead ends: 1060 [2025-03-16 18:01:52,597 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 155 GetRequests, 95 SyntacticMatches, 0 SemanticMatches, 60 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 751 ImplicationChecksByTransitivity, 3.7s TimeCoverageRelationStatistics Valid=656, Invalid=3126, Unknown=0, NotChecked=0, Total=3782 [2025-03-16 18:01:52,597 INFO L435 NwaCegarLoop]: 43 mSDtfsCounter, 62 mSDsluCounter, 197 mSDsCounter, 0 mSdLazyCounter, 970 mSolverCounterSat, 90 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 69 SdHoareTripleChecker+Valid, 240 SdHoareTripleChecker+Invalid, 1060 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 90 IncrementalHoareTripleChecker+Valid, 970 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.9s IncrementalHoareTripleChecker+Time [2025-03-16 18:01:52,598 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [69 Valid, 240 Invalid, 1060 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [90 Valid, 970 Invalid, 0 Unknown, 0 Unchecked, 1.9s Time] [2025-03-16 18:01:52,599 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1060 states. [2025-03-16 18:01:53,679 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1060 to 1029. [2025-03-16 18:01:53,681 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1029 states, 465 states have (on average 1.3182795698924732) internal successors, (613), 488 states have internal predecessors, (613), 505 states have call successors, (505), 58 states have call predecessors, (505), 58 states have return successors, (504), 482 states have call predecessors, (504), 504 states have call successors, (504) [2025-03-16 18:01:53,688 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1029 states to 1029 states and 1622 transitions. [2025-03-16 18:01:53,693 INFO L78 Accepts]: Start accepts. Automaton has 1029 states and 1622 transitions. Word has length 111 [2025-03-16 18:01:53,693 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:01:53,693 INFO L471 AbstractCegarLoop]: Abstraction has 1029 states and 1622 transitions. [2025-03-16 18:01:53,693 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 17 states have (on average 1.8823529411764706) internal successors, (32), 17 states have internal predecessors, (32), 8 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (12), 8 states have call predecessors, (12), 7 states have call successors, (12) [2025-03-16 18:01:53,694 INFO L276 IsEmpty]: Start isEmpty. Operand 1029 states and 1622 transitions. [2025-03-16 18:01:53,695 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 112 [2025-03-16 18:01:53,695 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:01:53,695 INFO L218 NwaCegarLoop]: trace histogram [17, 16, 16, 4, 4, 4, 4, 4, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:01:53,707 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Ended with exit code 0 [2025-03-16 18:01:53,900 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20,20 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:01:53,900 INFO L396 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:01:53,900 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:01:53,901 INFO L85 PathProgramCache]: Analyzing trace with hash 375631342, now seen corresponding path program 4 times [2025-03-16 18:01:53,904 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:01:53,905 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [145044696] [2025-03-16 18:01:53,905 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 18:01:53,905 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:01:53,909 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 111 statements into 2 equivalence classes. [2025-03-16 18:01:53,928 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 111 of 111 statements. [2025-03-16 18:01:53,929 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-16 18:01:53,929 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:01:53,929 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1486814974] [2025-03-16 18:01:53,931 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 18:01:53,931 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:01:53,931 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:01:53,937 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:01:53,942 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2025-03-16 18:01:53,986 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 111 statements into 2 equivalence classes. [2025-03-16 18:01:54,031 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 110 of 111 statements. [2025-03-16 18:01:54,032 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-03-16 18:01:54,032 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:01:54,033 INFO L256 TraceCheckSpWp]: Trace formula consists of 253 conjuncts, 84 conjuncts are in the unsatisfiable core [2025-03-16 18:01:54,035 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:01:55,033 INFO L134 CoverageAnalysis]: Checked inductivity of 557 backedges. 70 proven. 51 refuted. 0 times theorem prover too weak. 436 trivial. 0 not checked. [2025-03-16 18:01:55,033 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:01:56,600 INFO L134 CoverageAnalysis]: Checked inductivity of 557 backedges. 70 proven. 48 refuted. 0 times theorem prover too weak. 439 trivial. 0 not checked. [2025-03-16 18:01:56,600 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:01:56,600 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [145044696] [2025-03-16 18:01:56,600 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:01:56,600 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1486814974] [2025-03-16 18:01:56,600 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1486814974] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:01:56,600 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:01:56,600 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 19] total 38 [2025-03-16 18:01:56,600 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1160168101] [2025-03-16 18:01:56,600 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:01:56,601 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 38 states [2025-03-16 18:01:56,601 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:01:56,603 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 38 interpolants. [2025-03-16 18:01:56,607 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=182, Invalid=1224, Unknown=0, NotChecked=0, Total=1406 [2025-03-16 18:01:56,607 INFO L87 Difference]: Start difference. First operand 1029 states and 1622 transitions. Second operand has 38 states, 35 states have (on average 1.4857142857142858) internal successors, (52), 35 states have internal predecessors, (52), 13 states have call successors, (37), 3 states have call predecessors, (37), 3 states have return successors, (36), 11 states have call predecessors, (36), 11 states have call successors, (36) [2025-03-16 18:02:03,696 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers []