./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound10.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version e2fb8bed 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-scaling/hard2_unwindbound10.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 9f971bd1a6fba471cdece6d295ca31488341eb806ea8364f7549d05755c7a031 --- Real Ultimate output --- This is Ultimate 0.3.0-?-e2fb8be-m [2025-03-08 05:11:42,520 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-08 05:11:42,564 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-08 05:11:42,568 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-08 05:11:42,568 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-08 05:11:42,583 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-08 05:11:42,584 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-08 05:11:42,584 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-08 05:11:42,584 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-08 05:11:42,584 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-08 05:11:42,585 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-08 05:11:42,585 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-08 05:11:42,585 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-08 05:11:42,585 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-08 05:11:42,585 INFO L153 SettingsManager]: * Use SBE=true [2025-03-08 05:11:42,585 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-08 05:11:42,585 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-08 05:11:42,585 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-08 05:11:42,585 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-08 05:11:42,586 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-08 05:11:42,586 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-08 05:11:42,586 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-08 05:11:42,586 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-08 05:11:42,586 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-08 05:11:42,586 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-08 05:11:42,586 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-08 05:11:42,586 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-08 05:11:42,586 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-08 05:11:42,586 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-08 05:11:42,586 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-08 05:11:42,587 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-08 05:11:42,587 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-08 05:11:42,587 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-08 05:11:42,587 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-08 05:11:42,587 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-08 05:11:42,587 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-08 05:11:42,587 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-08 05:11:42,587 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-08 05:11:42,587 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-08 05:11:42,587 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-08 05:11:42,587 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-08 05:11:42,588 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-08 05:11:42,588 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-08 05:11:42,588 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 -> 9f971bd1a6fba471cdece6d295ca31488341eb806ea8364f7549d05755c7a031 [2025-03-08 05:11:42,823 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-08 05:11:42,831 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-08 05:11:42,833 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-08 05:11:42,834 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-08 05:11:42,835 INFO L274 PluginConnector]: CDTParser initialized [2025-03-08 05:11:42,836 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound10.c [2025-03-08 05:11:44,008 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/085742243/cf56b42bfe81461cac4fc1abc0551c71/FLAG68fb02732 [2025-03-08 05:11:44,225 INFO L384 CDTParser]: Found 1 translation units. [2025-03-08 05:11:44,226 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound10.c [2025-03-08 05:11:44,231 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/085742243/cf56b42bfe81461cac4fc1abc0551c71/FLAG68fb02732 [2025-03-08 05:11:44,575 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/085742243/cf56b42bfe81461cac4fc1abc0551c71 [2025-03-08 05:11:44,576 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-08 05:11:44,577 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-08 05:11:44,578 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-08 05:11:44,578 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-08 05:11:44,581 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-08 05:11:44,581 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.03 05:11:44" (1/1) ... [2025-03-08 05:11:44,582 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2458a042 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:11:44, skipping insertion in model container [2025-03-08 05:11:44,582 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.03 05:11:44" (1/1) ... [2025-03-08 05:11:44,590 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-08 05:11:44,679 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-scaling/hard2_unwindbound10.c[526,539] [2025-03-08 05:11:44,692 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-08 05:11:44,701 INFO L200 MainTranslator]: Completed pre-run [2025-03-08 05:11:44,709 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-scaling/hard2_unwindbound10.c[526,539] [2025-03-08 05:11:44,713 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-08 05:11:44,723 INFO L204 MainTranslator]: Completed translation [2025-03-08 05:11:44,724 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:11:44 WrapperNode [2025-03-08 05:11:44,724 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-08 05:11:44,725 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-08 05:11:44,726 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-08 05:11:44,726 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-08 05:11:44,731 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:11:44" (1/1) ... [2025-03-08 05:11:44,736 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:11:44" (1/1) ... [2025-03-08 05:11:44,746 INFO L138 Inliner]: procedures = 14, calls = 22, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 67 [2025-03-08 05:11:44,746 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-08 05:11:44,747 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-08 05:11:44,747 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-08 05:11:44,747 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-08 05:11:44,752 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:11:44" (1/1) ... [2025-03-08 05:11:44,752 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:11:44" (1/1) ... [2025-03-08 05:11:44,757 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:11:44" (1/1) ... [2025-03-08 05:11:44,765 INFO L175 MemorySlicer]: Split 10 memory accesses to 2 slices as follows [2, 8]. 80 percent of accesses are in the largest equivalence class. The 10 initializations are split as follows [2, 8]. The 0 writes are split as follows [0, 0]. [2025-03-08 05:11:44,767 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:11:44" (1/1) ... [2025-03-08 05:11:44,767 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:11:44" (1/1) ... [2025-03-08 05:11:44,769 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:11:44" (1/1) ... [2025-03-08 05:11:44,772 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:11:44" (1/1) ... [2025-03-08 05:11:44,773 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:11:44" (1/1) ... [2025-03-08 05:11:44,774 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:11:44" (1/1) ... [2025-03-08 05:11:44,775 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-08 05:11:44,778 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-08 05:11:44,778 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-08 05:11:44,778 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-08 05:11:44,778 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:11:44" (1/1) ... [2025-03-08 05:11:44,783 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-08 05:11:44,794 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:11:44,806 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-08 05:11:44,812 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-08 05:11:44,826 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-08 05:11:44,826 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-08 05:11:44,826 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2025-03-08 05:11:44,826 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-08 05:11:44,826 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-08 05:11:44,826 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-03-08 05:11:44,826 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-03-08 05:11:44,861 INFO L256 CfgBuilder]: Building ICFG [2025-03-08 05:11:44,863 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-08 05:11:44,968 INFO L? ?]: Removed 5 outVars from TransFormulas that were not future-live. [2025-03-08 05:11:44,968 INFO L307 CfgBuilder]: Performing block encoding [2025-03-08 05:11:44,976 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-08 05:11:44,976 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-08 05:11:44,976 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 08.03 05:11:44 BoogieIcfgContainer [2025-03-08 05:11:44,976 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-08 05:11:44,977 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-08 05:11:44,977 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-08 05:11:44,980 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-08 05:11:44,981 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 08.03 05:11:44" (1/3) ... [2025-03-08 05:11:44,981 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@45ec4f2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.03 05:11:44, skipping insertion in model container [2025-03-08 05:11:44,982 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:11:44" (2/3) ... [2025-03-08 05:11:44,982 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@45ec4f2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.03 05:11:44, skipping insertion in model container [2025-03-08 05:11:44,982 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 08.03 05:11:44" (3/3) ... [2025-03-08 05:11:44,983 INFO L128 eAbstractionObserver]: Analyzing ICFG hard2_unwindbound10.c [2025-03-08 05:11:44,993 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-08 05:11:44,995 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG hard2_unwindbound10.c that has 2 procedures, 26 locations, 1 initial locations, 2 loop locations, and 1 error locations. [2025-03-08 05:11:45,036 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-08 05:11:45,046 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;@4739f581, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-08 05:11:45,047 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-08 05:11:45,049 INFO L276 IsEmpty]: Start isEmpty. Operand has 26 states, 16 states have (on average 1.5625) internal successors, (25), 17 states have internal predecessors, (25), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2025-03-08 05:11:45,053 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2025-03-08 05:11:45,053 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:11:45,053 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:11:45,053 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:11:45,056 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:11:45,056 INFO L85 PathProgramCache]: Analyzing trace with hash 1337721167, now seen corresponding path program 1 times [2025-03-08 05:11:45,061 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:11:45,061 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1262423201] [2025-03-08 05:11:45,061 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:11:45,062 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:11:45,115 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-08 05:11:45,131 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-08 05:11:45,133 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:11:45,133 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:11:45,252 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-08 05:11:45,253 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:11:45,254 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1262423201] [2025-03-08 05:11:45,255 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1262423201] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:11:45,255 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:11:45,255 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-08 05:11:45,256 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1816935221] [2025-03-08 05:11:45,256 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:11:45,258 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-08 05:11:45,258 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:11:45,268 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-08 05:11:45,269 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-08 05:11:45,270 INFO L87 Difference]: Start difference. First operand has 26 states, 16 states have (on average 1.5625) internal successors, (25), 17 states have internal predecessors, (25), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand has 5 states, 5 states have (on average 1.4) internal successors, (7), 4 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-08 05:11:45,345 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:11:45,345 INFO L93 Difference]: Finished difference Result 64 states and 109 transitions. [2025-03-08 05:11:45,346 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-08 05:11:45,347 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.4) internal successors, (7), 4 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 8 [2025-03-08 05:11:45,347 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:11:45,351 INFO L225 Difference]: With dead ends: 64 [2025-03-08 05:11:45,352 INFO L226 Difference]: Without dead ends: 34 [2025-03-08 05:11:45,353 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 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-08 05:11:45,357 INFO L435 NwaCegarLoop]: 32 mSDtfsCounter, 13 mSDsluCounter, 80 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 112 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 22 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 05:11:45,359 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [20 Valid, 112 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 05:11:45,368 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2025-03-08 05:11:45,383 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 26. [2025-03-08 05:11:45,384 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 16 states have (on average 1.375) internal successors, (22), 17 states have internal predecessors, (22), 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-08 05:11:45,386 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 35 transitions. [2025-03-08 05:11:45,389 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 35 transitions. Word has length 8 [2025-03-08 05:11:45,389 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:11:45,389 INFO L471 AbstractCegarLoop]: Abstraction has 26 states and 35 transitions. [2025-03-08 05:11:45,390 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.4) internal successors, (7), 4 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-08 05:11:45,390 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 35 transitions. [2025-03-08 05:11:45,390 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2025-03-08 05:11:45,391 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:11:45,391 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:11:45,391 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-03-08 05:11:45,391 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:11:45,392 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:11:45,392 INFO L85 PathProgramCache]: Analyzing trace with hash 1248916916, now seen corresponding path program 1 times [2025-03-08 05:11:45,392 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:11:45,392 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [52244604] [2025-03-08 05:11:45,392 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:11:45,392 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:11:45,400 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-03-08 05:11:45,403 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-03-08 05:11:45,403 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:11:45,404 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:11:45,462 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-08 05:11:45,462 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:11:45,462 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [52244604] [2025-03-08 05:11:45,462 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [52244604] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:11:45,462 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:11:45,462 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2025-03-08 05:11:45,462 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1863264207] [2025-03-08 05:11:45,462 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:11:45,463 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2025-03-08 05:11:45,463 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:11:45,463 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2025-03-08 05:11:45,463 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-08 05:11:45,463 INFO L87 Difference]: Start difference. First operand 26 states and 35 transitions. Second operand has 4 states, 4 states have (on average 2.25) internal successors, (9), 3 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-08 05:11:45,485 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:11:45,485 INFO L93 Difference]: Finished difference Result 42 states and 57 transitions. [2025-03-08 05:11:45,486 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2025-03-08 05:11:45,486 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.25) internal successors, (9), 3 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 10 [2025-03-08 05:11:45,486 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:11:45,487 INFO L225 Difference]: With dead ends: 42 [2025-03-08 05:11:45,487 INFO L226 Difference]: Without dead ends: 28 [2025-03-08 05:11:45,487 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-08 05:11:45,488 INFO L435 NwaCegarLoop]: 30 mSDtfsCounter, 0 mSDsluCounter, 55 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 85 SdHoareTripleChecker+Invalid, 9 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 05:11:45,488 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 85 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 05:11:45,488 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2025-03-08 05:11:45,495 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 28. [2025-03-08 05:11:45,495 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 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-08 05:11:45,496 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 37 transitions. [2025-03-08 05:11:45,497 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 37 transitions. Word has length 10 [2025-03-08 05:11:45,497 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:11:45,497 INFO L471 AbstractCegarLoop]: Abstraction has 28 states and 37 transitions. [2025-03-08 05:11:45,497 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.25) internal successors, (9), 3 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-08 05:11:45,497 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 37 transitions. [2025-03-08 05:11:45,498 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2025-03-08 05:11:45,498 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:11:45,498 INFO L218 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:11:45,498 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-03-08 05:11:45,498 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:11:45,498 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:11:45,498 INFO L85 PathProgramCache]: Analyzing trace with hash -1610903053, now seen corresponding path program 1 times [2025-03-08 05:11:45,499 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:11:45,499 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1268635663] [2025-03-08 05:11:45,499 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:11:45,499 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:11:45,505 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 13 statements into 1 equivalence classes. [2025-03-08 05:11:45,509 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 13 of 13 statements. [2025-03-08 05:11:45,509 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:11:45,509 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:11:45,573 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-08 05:11:45,573 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:11:45,573 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1268635663] [2025-03-08 05:11:45,574 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1268635663] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:11:45,574 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:11:45,574 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-08 05:11:45,574 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1296542490] [2025-03-08 05:11:45,574 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:11:45,575 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-08 05:11:45,575 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:11:45,576 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-08 05:11:45,577 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-08 05:11:45,577 INFO L87 Difference]: Start difference. First operand 28 states and 37 transitions. Second operand has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-08 05:11:45,627 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:11:45,627 INFO L93 Difference]: Finished difference Result 42 states and 56 transitions. [2025-03-08 05:11:45,627 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-08 05:11:45,627 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), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 13 [2025-03-08 05:11:45,628 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:11:45,628 INFO L225 Difference]: With dead ends: 42 [2025-03-08 05:11:45,628 INFO L226 Difference]: Without dead ends: 40 [2025-03-08 05:11:45,629 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 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-08 05:11:45,630 INFO L435 NwaCegarLoop]: 28 mSDtfsCounter, 12 mSDsluCounter, 66 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 94 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-08 05:11:45,630 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 94 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 05:11:45,632 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2025-03-08 05:11:45,636 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 32. [2025-03-08 05:11:45,636 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 21 states have (on average 1.2857142857142858) internal successors, (27), 22 states have internal predecessors, (27), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-03-08 05:11:45,637 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 40 transitions. [2025-03-08 05:11:45,637 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 40 transitions. Word has length 13 [2025-03-08 05:11:45,637 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:11:45,637 INFO L471 AbstractCegarLoop]: Abstraction has 32 states and 40 transitions. [2025-03-08 05:11:45,637 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), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-08 05:11:45,638 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 40 transitions. [2025-03-08 05:11:45,638 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2025-03-08 05:11:45,638 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:11:45,638 INFO L218 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:11:45,638 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2025-03-08 05:11:45,638 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:11:45,638 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:11:45,639 INFO L85 PathProgramCache]: Analyzing trace with hash 1890824207, now seen corresponding path program 1 times [2025-03-08 05:11:45,639 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:11:45,639 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [637972535] [2025-03-08 05:11:45,639 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:11:45,639 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:11:45,642 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 18 statements into 1 equivalence classes. [2025-03-08 05:11:45,646 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 18 of 18 statements. [2025-03-08 05:11:45,647 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:11:45,647 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:11:45,648 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1154084049] [2025-03-08 05:11:45,648 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:11:45,648 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:11:45,648 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:11:45,650 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-08 05:11:45,652 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-08 05:11:45,682 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 18 statements into 1 equivalence classes. [2025-03-08 05:11:45,695 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 18 of 18 statements. [2025-03-08 05:11:45,695 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:11:45,695 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:11:45,696 INFO L256 TraceCheckSpWp]: Trace formula consists of 83 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-08 05:11:45,699 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:11:45,796 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-08 05:11:45,797 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-08 05:11:45,797 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:11:45,797 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [637972535] [2025-03-08 05:11:45,797 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:11:45,797 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1154084049] [2025-03-08 05:11:45,797 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1154084049] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:11:45,797 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:11:45,798 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-08 05:11:45,798 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [215172475] [2025-03-08 05:11:45,798 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:11:45,798 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-08 05:11:45,798 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:11:45,798 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-08 05:11:45,798 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-08 05:11:45,798 INFO L87 Difference]: Start difference. First operand 32 states and 40 transitions. Second operand has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 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-08 05:11:45,841 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:11:45,841 INFO L93 Difference]: Finished difference Result 61 states and 83 transitions. [2025-03-08 05:11:45,841 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-08 05:11:45,841 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), 1 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-08 05:11:45,841 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:11:45,842 INFO L225 Difference]: With dead ends: 61 [2025-03-08 05:11:45,842 INFO L226 Difference]: Without dead ends: 46 [2025-03-08 05:11:45,842 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 14 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-08 05:11:45,842 INFO L435 NwaCegarLoop]: 28 mSDtfsCounter, 7 mSDsluCounter, 70 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 98 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 37 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 05:11:45,842 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 98 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 05:11:45,843 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2025-03-08 05:11:45,847 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 46. [2025-03-08 05:11:45,847 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 28 states have (on average 1.2857142857142858) internal successors, (36), 30 states have internal predecessors, (36), 13 states have call successors, (13), 4 states have call predecessors, (13), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2025-03-08 05:11:45,848 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 60 transitions. [2025-03-08 05:11:45,848 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 60 transitions. Word has length 18 [2025-03-08 05:11:45,848 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:11:45,848 INFO L471 AbstractCegarLoop]: Abstraction has 46 states and 60 transitions. [2025-03-08 05:11:45,848 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), 1 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-08 05:11:45,848 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 60 transitions. [2025-03-08 05:11:45,849 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2025-03-08 05:11:45,849 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:11:45,849 INFO L218 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:11:45,855 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-08 05:11:46,049 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:11:46,050 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:11:46,050 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:11:46,050 INFO L85 PathProgramCache]: Analyzing trace with hash -1939108053, now seen corresponding path program 1 times [2025-03-08 05:11:46,050 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:11:46,051 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1036532307] [2025-03-08 05:11:46,051 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:11:46,051 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:11:46,054 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 26 statements into 1 equivalence classes. [2025-03-08 05:11:46,060 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 26 of 26 statements. [2025-03-08 05:11:46,064 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:11:46,064 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:11:46,065 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [406273059] [2025-03-08 05:11:46,066 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:11:46,066 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:11:46,066 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:11:46,067 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-08 05:11:46,069 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-08 05:11:46,090 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 26 statements into 1 equivalence classes. [2025-03-08 05:11:46,101 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 26 of 26 statements. [2025-03-08 05:11:46,102 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:11:46,102 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:11:46,102 INFO L256 TraceCheckSpWp]: Trace formula consists of 98 conjuncts, 15 conjuncts are in the unsatisfiable core [2025-03-08 05:11:46,103 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:11:46,175 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 5 proven. 7 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2025-03-08 05:11:46,176 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:11:46,306 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 5 proven. 7 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2025-03-08 05:11:46,306 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:11:46,306 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1036532307] [2025-03-08 05:11:46,306 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:11:46,306 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [406273059] [2025-03-08 05:11:46,307 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [406273059] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:11:46,307 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-08 05:11:46,307 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2025-03-08 05:11:46,307 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [163039633] [2025-03-08 05:11:46,307 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-08 05:11:46,307 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-03-08 05:11:46,307 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:11:46,308 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-03-08 05:11:46,308 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=67, Unknown=0, NotChecked=0, Total=90 [2025-03-08 05:11:46,308 INFO L87 Difference]: Start difference. First operand 46 states and 60 transitions. Second operand has 10 states, 10 states have (on average 2.3) internal successors, (23), 9 states have internal predecessors, (23), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-08 05:11:46,400 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:11:46,400 INFO L93 Difference]: Finished difference Result 64 states and 86 transitions. [2025-03-08 05:11:46,400 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-03-08 05:11:46,400 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.3) internal successors, (23), 9 states have internal predecessors, (23), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) Word has length 26 [2025-03-08 05:11:46,400 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:11:46,402 INFO L225 Difference]: With dead ends: 64 [2025-03-08 05:11:46,402 INFO L226 Difference]: Without dead ends: 61 [2025-03-08 05:11:46,402 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 41 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=31, Invalid=79, Unknown=0, NotChecked=0, Total=110 [2025-03-08 05:11:46,402 INFO L435 NwaCegarLoop]: 19 mSDtfsCounter, 22 mSDsluCounter, 61 mSDsCounter, 0 mSdLazyCounter, 79 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 80 SdHoareTripleChecker+Invalid, 90 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 79 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:11:46,402 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [26 Valid, 80 Invalid, 90 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 79 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:11:46,403 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 61 states. [2025-03-08 05:11:46,408 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 61 to 56. [2025-03-08 05:11:46,408 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 56 states, 35 states have (on average 1.2857142857142858) internal successors, (45), 37 states have internal predecessors, (45), 15 states have call successors, (15), 5 states have call predecessors, (15), 5 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2025-03-08 05:11:46,409 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 74 transitions. [2025-03-08 05:11:46,409 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 74 transitions. Word has length 26 [2025-03-08 05:11:46,409 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:11:46,409 INFO L471 AbstractCegarLoop]: Abstraction has 56 states and 74 transitions. [2025-03-08 05:11:46,409 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.3) internal successors, (23), 9 states have internal predecessors, (23), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-08 05:11:46,409 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 74 transitions. [2025-03-08 05:11:46,410 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2025-03-08 05:11:46,410 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:11:46,410 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:11:46,416 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2025-03-08 05:11:46,614 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:11:46,614 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:11:46,614 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:11:46,615 INFO L85 PathProgramCache]: Analyzing trace with hash 1363596918, now seen corresponding path program 1 times [2025-03-08 05:11:46,615 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:11:46,615 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [189195463] [2025-03-08 05:11:46,615 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:11:46,615 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:11:46,619 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 33 statements into 1 equivalence classes. [2025-03-08 05:11:46,627 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 33 of 33 statements. [2025-03-08 05:11:46,627 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:11:46,627 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:11:46,679 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-08 05:11:46,680 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:11:46,680 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [189195463] [2025-03-08 05:11:46,680 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [189195463] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:11:46,680 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [509228524] [2025-03-08 05:11:46,680 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:11:46,680 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:11:46,680 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:11:46,681 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-08 05:11:46,682 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-08 05:11:46,702 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 33 statements into 1 equivalence classes. [2025-03-08 05:11:46,714 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 33 of 33 statements. [2025-03-08 05:11:46,714 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:11:46,714 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:11:46,715 INFO L256 TraceCheckSpWp]: Trace formula consists of 116 conjuncts, 5 conjuncts are in the unsatisfiable core [2025-03-08 05:11:46,716 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:11:46,756 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 18 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2025-03-08 05:11:46,756 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:11:46,796 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-08 05:11:46,797 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [509228524] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:11:46,797 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 05:11:46,797 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 4, 5] total 8 [2025-03-08 05:11:46,797 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1089863177] [2025-03-08 05:11:46,797 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 05:11:46,797 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-03-08 05:11:46,797 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:11:46,797 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-08 05:11:46,798 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2025-03-08 05:11:46,798 INFO L87 Difference]: Start difference. First operand 56 states and 74 transitions. Second operand has 8 states, 8 states have (on average 3.375) internal successors, (27), 8 states have internal predecessors, (27), 3 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2025-03-08 05:11:46,892 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:11:46,893 INFO L93 Difference]: Finished difference Result 155 states and 190 transitions. [2025-03-08 05:11:46,893 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-03-08 05:11:46,893 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.375) internal successors, (27), 8 states have internal predecessors, (27), 3 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) Word has length 33 [2025-03-08 05:11:46,893 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:11:46,894 INFO L225 Difference]: With dead ends: 155 [2025-03-08 05:11:46,894 INFO L226 Difference]: Without dead ends: 130 [2025-03-08 05:11:46,895 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 72 GetRequests, 63 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=40, Invalid=70, Unknown=0, NotChecked=0, Total=110 [2025-03-08 05:11:46,895 INFO L435 NwaCegarLoop]: 31 mSDtfsCounter, 47 mSDsluCounter, 113 mSDsCounter, 0 mSdLazyCounter, 56 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 47 SdHoareTripleChecker+Valid, 144 SdHoareTripleChecker+Invalid, 59 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 56 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:11:46,895 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [47 Valid, 144 Invalid, 59 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 56 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:11:46,895 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2025-03-08 05:11:46,915 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 123. [2025-03-08 05:11:46,916 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 123 states, 79 states have (on average 1.2025316455696202) internal successors, (95), 83 states have internal predecessors, (95), 27 states have call successors, (27), 16 states have call predecessors, (27), 16 states have return successors, (24), 23 states have call predecessors, (24), 24 states have call successors, (24) [2025-03-08 05:11:46,917 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 123 states to 123 states and 146 transitions. [2025-03-08 05:11:46,920 INFO L78 Accepts]: Start accepts. Automaton has 123 states and 146 transitions. Word has length 33 [2025-03-08 05:11:46,920 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:11:46,920 INFO L471 AbstractCegarLoop]: Abstraction has 123 states and 146 transitions. [2025-03-08 05:11:46,921 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.375) internal successors, (27), 8 states have internal predecessors, (27), 3 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2025-03-08 05:11:46,921 INFO L276 IsEmpty]: Start isEmpty. Operand 123 states and 146 transitions. [2025-03-08 05:11:46,921 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2025-03-08 05:11:46,922 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:11:46,922 INFO L218 NwaCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1] [2025-03-08 05:11:46,928 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2025-03-08 05:11:47,126 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:11:47,126 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:11:47,126 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:11:47,126 INFO L85 PathProgramCache]: Analyzing trace with hash 1138305543, now seen corresponding path program 1 times [2025-03-08 05:11:47,127 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:11:47,127 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1417713586] [2025-03-08 05:11:47,128 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:11:47,128 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:11:47,131 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 36 statements into 1 equivalence classes. [2025-03-08 05:11:47,138 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 36 of 36 statements. [2025-03-08 05:11:47,138 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:11:47,138 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:11:47,138 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1986334600] [2025-03-08 05:11:47,138 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:11:47,139 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:11:47,139 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:11:47,142 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-08 05:11:47,143 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-08 05:11:47,162 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 36 statements into 1 equivalence classes. [2025-03-08 05:11:47,174 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 36 of 36 statements. [2025-03-08 05:11:47,174 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:11:47,174 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:11:47,174 INFO L256 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-03-08 05:11:47,176 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:11:47,257 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 5 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2025-03-08 05:11:47,258 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:11:47,316 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2025-03-08 05:11:47,316 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:11:47,316 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1417713586] [2025-03-08 05:11:47,316 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:11:47,316 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1986334600] [2025-03-08 05:11:47,317 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1986334600] provided 1 perfect and 1 imperfect interpolant sequences [2025-03-08 05:11:47,317 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-08 05:11:47,317 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2025-03-08 05:11:47,317 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1185875936] [2025-03-08 05:11:47,317 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:11:47,317 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-08 05:11:47,317 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:11:47,318 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-08 05:11:47,318 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2025-03-08 05:11:47,318 INFO L87 Difference]: Start difference. First operand 123 states and 146 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2025-03-08 05:11:48,271 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:11:48,272 INFO L93 Difference]: Finished difference Result 146 states and 174 transitions. [2025-03-08 05:11:48,274 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-08 05:11:48,274 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 36 [2025-03-08 05:11:48,274 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:11:48,275 INFO L225 Difference]: With dead ends: 146 [2025-03-08 05:11:48,275 INFO L226 Difference]: Without dead ends: 140 [2025-03-08 05:11:48,275 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 71 GetRequests, 63 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-08 05:11:48,276 INFO L435 NwaCegarLoop]: 28 mSDtfsCounter, 8 mSDsluCounter, 64 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 92 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2025-03-08 05:11:48,276 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 92 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2025-03-08 05:11:48,276 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 140 states. [2025-03-08 05:11:48,289 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 140 to 132. [2025-03-08 05:11:48,290 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 132 states, 86 states have (on average 1.1744186046511629) internal successors, (101), 90 states have internal predecessors, (101), 28 states have call successors, (28), 18 states have call predecessors, (28), 17 states have return successors, (26), 23 states have call predecessors, (26), 26 states have call successors, (26) [2025-03-08 05:11:48,291 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 132 states to 132 states and 155 transitions. [2025-03-08 05:11:48,291 INFO L78 Accepts]: Start accepts. Automaton has 132 states and 155 transitions. Word has length 36 [2025-03-08 05:11:48,291 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:11:48,291 INFO L471 AbstractCegarLoop]: Abstraction has 132 states and 155 transitions. [2025-03-08 05:11:48,291 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2025-03-08 05:11:48,291 INFO L276 IsEmpty]: Start isEmpty. Operand 132 states and 155 transitions. [2025-03-08 05:11:48,293 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2025-03-08 05:11:48,293 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:11:48,293 INFO L218 NwaCegarLoop]: trace histogram [7, 6, 6, 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-08 05:11:48,299 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2025-03-08 05:11:48,494 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:11:48,494 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:11:48,494 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:11:48,494 INFO L85 PathProgramCache]: Analyzing trace with hash -1167569937, now seen corresponding path program 1 times [2025-03-08 05:11:48,494 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:11:48,495 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1367196141] [2025-03-08 05:11:48,495 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:11:48,495 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:11:48,498 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 42 statements into 1 equivalence classes. [2025-03-08 05:11:48,503 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 42 of 42 statements. [2025-03-08 05:11:48,503 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:11:48,503 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:11:48,597 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2025-03-08 05:11:48,598 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:11:48,598 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1367196141] [2025-03-08 05:11:48,598 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1367196141] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:11:48,598 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:11:48,598 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-08 05:11:48,598 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [925785077] [2025-03-08 05:11:48,598 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:11:48,598 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-08 05:11:48,598 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:11:48,599 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-08 05:11:48,599 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-08 05:11:48,599 INFO L87 Difference]: Start difference. First operand 132 states and 155 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 1 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2025-03-08 05:11:48,641 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:11:48,642 INFO L93 Difference]: Finished difference Result 137 states and 159 transitions. [2025-03-08 05:11:48,643 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-08 05:11:48,643 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), 1 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) Word has length 42 [2025-03-08 05:11:48,643 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:11:48,644 INFO L225 Difference]: With dead ends: 137 [2025-03-08 05:11:48,644 INFO L226 Difference]: Without dead ends: 118 [2025-03-08 05:11:48,644 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 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-08 05:11:48,644 INFO L435 NwaCegarLoop]: 32 mSDtfsCounter, 1 mSDsluCounter, 79 mSDsCounter, 0 mSdLazyCounter, 24 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 111 SdHoareTripleChecker+Invalid, 24 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 24 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 05:11:48,645 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 111 Invalid, 24 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 05:11:48,646 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 118 states. [2025-03-08 05:11:48,663 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 118 to 118. [2025-03-08 05:11:48,664 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 118 states, 77 states have (on average 1.1818181818181819) internal successors, (91), 80 states have internal predecessors, (91), 25 states have call successors, (25), 16 states have call predecessors, (25), 15 states have return successors, (23), 21 states have call predecessors, (23), 23 states have call successors, (23) [2025-03-08 05:11:48,665 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 139 transitions. [2025-03-08 05:11:48,666 INFO L78 Accepts]: Start accepts. Automaton has 118 states and 139 transitions. Word has length 42 [2025-03-08 05:11:48,666 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:11:48,666 INFO L471 AbstractCegarLoop]: Abstraction has 118 states and 139 transitions. [2025-03-08 05:11:48,666 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), 1 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2025-03-08 05:11:48,666 INFO L276 IsEmpty]: Start isEmpty. Operand 118 states and 139 transitions. [2025-03-08 05:11:48,667 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2025-03-08 05:11:48,668 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:11:48,668 INFO L218 NwaCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:11:48,668 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7 [2025-03-08 05:11:48,668 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:11:48,669 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:11:48,669 INFO L85 PathProgramCache]: Analyzing trace with hash -2110847750, now seen corresponding path program 1 times [2025-03-08 05:11:48,669 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:11:48,669 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [224967895] [2025-03-08 05:11:48,669 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:11:48,669 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:11:48,674 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 49 statements into 1 equivalence classes. [2025-03-08 05:11:48,679 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 49 of 49 statements. [2025-03-08 05:11:48,680 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:11:48,680 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:11:48,738 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 14 proven. 6 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2025-03-08 05:11:48,738 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:11:48,739 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [224967895] [2025-03-08 05:11:48,739 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [224967895] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:11:48,739 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1228445140] [2025-03-08 05:11:48,739 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:11:48,739 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:11:48,739 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:11:48,741 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-08 05:11:48,743 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-08 05:11:48,768 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 49 statements into 1 equivalence classes. [2025-03-08 05:11:48,782 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 49 of 49 statements. [2025-03-08 05:11:48,782 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:11:48,782 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:11:48,783 INFO L256 TraceCheckSpWp]: Trace formula consists of 144 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-08 05:11:48,785 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:11:48,832 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 36 proven. 42 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2025-03-08 05:11:48,833 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:11:48,894 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 14 proven. 6 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2025-03-08 05:11:48,894 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1228445140] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:11:48,894 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 05:11:48,894 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5, 6] total 10 [2025-03-08 05:11:48,894 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1432598190] [2025-03-08 05:11:48,894 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 05:11:48,895 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-03-08 05:11:48,895 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:11:48,895 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-03-08 05:11:48,895 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2025-03-08 05:11:48,895 INFO L87 Difference]: Start difference. First operand 118 states and 139 transitions. Second operand has 10 states, 10 states have (on average 3.4) internal successors, (34), 10 states have internal predecessors, (34), 5 states have call successors, (21), 4 states have call predecessors, (21), 4 states have return successors, (20), 5 states have call predecessors, (20), 5 states have call successors, (20) [2025-03-08 05:11:49,037 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:11:49,037 INFO L93 Difference]: Finished difference Result 241 states and 294 transitions. [2025-03-08 05:11:49,038 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2025-03-08 05:11:49,039 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.4) internal successors, (34), 10 states have internal predecessors, (34), 5 states have call successors, (21), 4 states have call predecessors, (21), 4 states have return successors, (20), 5 states have call predecessors, (20), 5 states have call successors, (20) Word has length 49 [2025-03-08 05:11:49,039 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:11:49,040 INFO L225 Difference]: With dead ends: 241 [2025-03-08 05:11:49,040 INFO L226 Difference]: Without dead ends: 220 [2025-03-08 05:11:49,040 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 105 GetRequests, 94 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=52, Invalid=104, Unknown=0, NotChecked=0, Total=156 [2025-03-08 05:11:49,041 INFO L435 NwaCegarLoop]: 31 mSDtfsCounter, 77 mSDsluCounter, 156 mSDsCounter, 0 mSdLazyCounter, 98 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 77 SdHoareTripleChecker+Valid, 187 SdHoareTripleChecker+Invalid, 111 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 98 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:11:49,041 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [77 Valid, 187 Invalid, 111 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 98 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:11:49,041 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 220 states. [2025-03-08 05:11:49,056 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 220 to 213. [2025-03-08 05:11:49,066 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 213 states, 138 states have (on average 1.1956521739130435) internal successors, (165), 147 states have internal predecessors, (165), 49 states have call successors, (49), 26 states have call predecessors, (49), 25 states have return successors, (45), 39 states have call predecessors, (45), 45 states have call successors, (45) [2025-03-08 05:11:49,067 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 213 states to 213 states and 259 transitions. [2025-03-08 05:11:49,068 INFO L78 Accepts]: Start accepts. Automaton has 213 states and 259 transitions. Word has length 49 [2025-03-08 05:11:49,068 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:11:49,068 INFO L471 AbstractCegarLoop]: Abstraction has 213 states and 259 transitions. [2025-03-08 05:11:49,068 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.4) internal successors, (34), 10 states have internal predecessors, (34), 5 states have call successors, (21), 4 states have call predecessors, (21), 4 states have return successors, (20), 5 states have call predecessors, (20), 5 states have call successors, (20) [2025-03-08 05:11:49,068 INFO L276 IsEmpty]: Start isEmpty. Operand 213 states and 259 transitions. [2025-03-08 05:11:49,070 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2025-03-08 05:11:49,071 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:11:49,071 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:11:49,077 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2025-03-08 05:11:49,272 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:11:49,272 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:11:49,273 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:11:49,273 INFO L85 PathProgramCache]: Analyzing trace with hash -1455298504, now seen corresponding path program 1 times [2025-03-08 05:11:49,274 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:11:49,274 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [228221704] [2025-03-08 05:11:49,274 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:11:49,274 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:11:49,279 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 58 statements into 1 equivalence classes. [2025-03-08 05:11:49,302 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 58 of 58 statements. [2025-03-08 05:11:49,303 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:11:49,303 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:11:49,304 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1510322133] [2025-03-08 05:11:49,304 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:11:49,305 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:11:49,305 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:11:49,306 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-08 05:11:49,308 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-08 05:11:49,332 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 58 statements into 1 equivalence classes. [2025-03-08 05:11:49,348 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 58 of 58 statements. [2025-03-08 05:11:49,348 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:11:49,348 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:11:49,349 INFO L256 TraceCheckSpWp]: Trace formula consists of 168 conjuncts, 33 conjuncts are in the unsatisfiable core [2025-03-08 05:11:49,354 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:11:49,585 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 15 proven. 31 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2025-03-08 05:11:49,585 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:11:50,667 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 15 proven. 31 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2025-03-08 05:11:50,667 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:11:50,667 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [228221704] [2025-03-08 05:11:50,667 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:11:50,667 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1510322133] [2025-03-08 05:11:50,667 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1510322133] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:11:50,667 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-08 05:11:50,667 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2025-03-08 05:11:50,668 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1652046937] [2025-03-08 05:11:50,668 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-08 05:11:50,668 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2025-03-08 05:11:50,668 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:11:50,668 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2025-03-08 05:11:50,668 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=43, Invalid=167, Unknown=0, NotChecked=0, Total=210 [2025-03-08 05:11:50,668 INFO L87 Difference]: Start difference. First operand 213 states and 259 transitions. Second operand has 15 states, 15 states have (on average 2.6666666666666665) internal successors, (40), 14 states have internal predecessors, (40), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) [2025-03-08 05:11:51,229 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:11:51,229 INFO L93 Difference]: Finished difference Result 359 states and 460 transitions. [2025-03-08 05:11:51,229 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2025-03-08 05:11:51,230 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.6666666666666665) internal successors, (40), 14 states have internal predecessors, (40), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) Word has length 58 [2025-03-08 05:11:51,230 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:11:51,231 INFO L225 Difference]: With dead ends: 359 [2025-03-08 05:11:51,231 INFO L226 Difference]: Without dead ends: 298 [2025-03-08 05:11:51,232 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 118 GetRequests, 101 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=76, Invalid=266, Unknown=0, NotChecked=0, Total=342 [2025-03-08 05:11:51,232 INFO L435 NwaCegarLoop]: 40 mSDtfsCounter, 48 mSDsluCounter, 258 mSDsCounter, 0 mSdLazyCounter, 292 mSolverCounterSat, 81 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 54 SdHoareTripleChecker+Valid, 298 SdHoareTripleChecker+Invalid, 373 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 81 IncrementalHoareTripleChecker+Valid, 292 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-03-08 05:11:51,232 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [54 Valid, 298 Invalid, 373 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [81 Valid, 292 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-03-08 05:11:51,233 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 298 states. [2025-03-08 05:11:51,267 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 298 to 272. [2025-03-08 05:11:51,268 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 272 states, 185 states have (on average 1.227027027027027) internal successors, (227), 192 states have internal predecessors, (227), 57 states have call successors, (57), 29 states have call predecessors, (57), 29 states have return successors, (55), 50 states have call predecessors, (55), 55 states have call successors, (55) [2025-03-08 05:11:51,270 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 272 states to 272 states and 339 transitions. [2025-03-08 05:11:51,270 INFO L78 Accepts]: Start accepts. Automaton has 272 states and 339 transitions. Word has length 58 [2025-03-08 05:11:51,271 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:11:51,271 INFO L471 AbstractCegarLoop]: Abstraction has 272 states and 339 transitions. [2025-03-08 05:11:51,271 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.6666666666666665) internal successors, (40), 14 states have internal predecessors, (40), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) [2025-03-08 05:11:51,271 INFO L276 IsEmpty]: Start isEmpty. Operand 272 states and 339 transitions. [2025-03-08 05:11:51,273 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2025-03-08 05:11:51,273 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:11:51,273 INFO L218 NwaCegarLoop]: trace histogram [11, 10, 10, 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-08 05:11:51,279 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2025-03-08 05:11:51,473 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:11:51,474 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:11:51,474 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:11:51,474 INFO L85 PathProgramCache]: Analyzing trace with hash -284772378, now seen corresponding path program 1 times [2025-03-08 05:11:51,474 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:11:51,475 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [477344549] [2025-03-08 05:11:51,475 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:11:51,475 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:11:51,479 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 69 statements into 1 equivalence classes. [2025-03-08 05:11:51,494 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 69 of 69 statements. [2025-03-08 05:11:51,494 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:11:51,494 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:11:51,497 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [836262760] [2025-03-08 05:11:51,497 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:11:51,497 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:11:51,498 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:11:51,499 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-08 05:11:51,501 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-08 05:11:51,521 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 69 statements into 1 equivalence classes. [2025-03-08 05:11:51,540 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 69 of 69 statements. [2025-03-08 05:11:51,541 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:11:51,541 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:11:51,542 INFO L256 TraceCheckSpWp]: Trace formula consists of 188 conjuncts, 35 conjuncts are in the unsatisfiable core [2025-03-08 05:11:51,544 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:11:51,743 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 19 proven. 39 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2025-03-08 05:11:51,743 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:11:52,164 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 19 proven. 39 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2025-03-08 05:11:52,164 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:11:52,164 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [477344549] [2025-03-08 05:11:52,164 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:11:52,164 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [836262760] [2025-03-08 05:11:52,165 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [836262760] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:11:52,165 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-08 05:11:52,165 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9] total 16 [2025-03-08 05:11:52,165 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1283011680] [2025-03-08 05:11:52,165 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-08 05:11:52,165 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-03-08 05:11:52,165 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:11:52,165 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-03-08 05:11:52,166 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=187, Unknown=0, NotChecked=0, Total=240 [2025-03-08 05:11:52,166 INFO L87 Difference]: Start difference. First operand 272 states and 339 transitions. Second operand has 16 states, 14 states have (on average 3.0) internal successors, (42), 15 states have internal predecessors, (42), 8 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 5 states have call predecessors, (20), 6 states have call successors, (20) [2025-03-08 05:11:52,437 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:11:52,437 INFO L93 Difference]: Finished difference Result 339 states and 424 transitions. [2025-03-08 05:11:52,437 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2025-03-08 05:11:52,438 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 14 states have (on average 3.0) internal successors, (42), 15 states have internal predecessors, (42), 8 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 5 states have call predecessors, (20), 6 states have call successors, (20) Word has length 69 [2025-03-08 05:11:52,439 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:11:52,440 INFO L225 Difference]: With dead ends: 339 [2025-03-08 05:11:52,441 INFO L226 Difference]: Without dead ends: 271 [2025-03-08 05:11:52,442 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 139 GetRequests, 122 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=79, Invalid=263, Unknown=0, NotChecked=0, Total=342 [2025-03-08 05:11:52,442 INFO L435 NwaCegarLoop]: 35 mSDtfsCounter, 26 mSDsluCounter, 173 mSDsCounter, 0 mSdLazyCounter, 221 mSolverCounterSat, 35 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 208 SdHoareTripleChecker+Invalid, 256 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 35 IncrementalHoareTripleChecker+Valid, 221 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-08 05:11:52,442 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [31 Valid, 208 Invalid, 256 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [35 Valid, 221 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-08 05:11:52,443 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 271 states. [2025-03-08 05:11:52,476 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 271 to 243. [2025-03-08 05:11:52,477 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 243 states, 166 states have (on average 1.180722891566265) internal successors, (196), 171 states have internal predecessors, (196), 47 states have call successors, (47), 30 states have call predecessors, (47), 29 states have return successors, (45), 41 states have call predecessors, (45), 45 states have call successors, (45) [2025-03-08 05:11:52,478 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 243 states to 243 states and 288 transitions. [2025-03-08 05:11:52,478 INFO L78 Accepts]: Start accepts. Automaton has 243 states and 288 transitions. Word has length 69 [2025-03-08 05:11:52,478 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:11:52,478 INFO L471 AbstractCegarLoop]: Abstraction has 243 states and 288 transitions. [2025-03-08 05:11:52,479 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 14 states have (on average 3.0) internal successors, (42), 15 states have internal predecessors, (42), 8 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 5 states have call predecessors, (20), 6 states have call successors, (20) [2025-03-08 05:11:52,479 INFO L276 IsEmpty]: Start isEmpty. Operand 243 states and 288 transitions. [2025-03-08 05:11:52,480 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2025-03-08 05:11:52,480 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:11:52,480 INFO L218 NwaCegarLoop]: trace histogram [12, 11, 11, 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] [2025-03-08 05:11:52,487 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-08 05:11:52,685 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:11:52,685 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:11:52,686 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:11:52,686 INFO L85 PathProgramCache]: Analyzing trace with hash -1844647172, now seen corresponding path program 1 times [2025-03-08 05:11:52,686 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:11:52,687 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1951567520] [2025-03-08 05:11:52,687 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:11:52,687 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:11:52,691 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 74 statements into 1 equivalence classes. [2025-03-08 05:11:52,700 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 74 of 74 statements. [2025-03-08 05:11:52,700 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:11:52,700 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:11:52,969 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 22 proven. 11 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2025-03-08 05:11:52,969 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:11:52,969 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1951567520] [2025-03-08 05:11:52,969 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1951567520] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:11:52,970 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [772747516] [2025-03-08 05:11:52,970 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:11:52,970 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:11:52,970 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:11:52,972 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-08 05:11:52,973 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-08 05:11:52,995 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 74 statements into 1 equivalence classes. [2025-03-08 05:11:53,013 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 74 of 74 statements. [2025-03-08 05:11:53,013 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:11:53,013 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:11:53,014 INFO L256 TraceCheckSpWp]: Trace formula consists of 197 conjuncts, 19 conjuncts are in the unsatisfiable core [2025-03-08 05:11:53,016 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:11:53,131 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 22 proven. 11 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2025-03-08 05:11:53,131 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:11:53,422 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 22 proven. 11 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2025-03-08 05:11:53,422 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [772747516] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:11:53,422 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 05:11:53,422 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 13 [2025-03-08 05:11:53,422 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1306140734] [2025-03-08 05:11:53,422 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 05:11:53,423 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2025-03-08 05:11:53,423 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:11:53,423 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2025-03-08 05:11:53,424 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=120, Unknown=0, NotChecked=0, Total=156 [2025-03-08 05:11:53,424 INFO L87 Difference]: Start difference. First operand 243 states and 288 transitions. Second operand has 13 states, 13 states have (on average 3.923076923076923) internal successors, (51), 11 states have internal predecessors, (51), 7 states have call successors, (35), 3 states have call predecessors, (35), 1 states have return successors, (32), 7 states have call predecessors, (32), 7 states have call successors, (32) [2025-03-08 05:11:53,577 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:11:53,578 INFO L93 Difference]: Finished difference Result 267 states and 315 transitions. [2025-03-08 05:11:53,578 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-03-08 05:11:53,578 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 3.923076923076923) internal successors, (51), 11 states have internal predecessors, (51), 7 states have call successors, (35), 3 states have call predecessors, (35), 1 states have return successors, (32), 7 states have call predecessors, (32), 7 states have call successors, (32) Word has length 74 [2025-03-08 05:11:53,578 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:11:53,579 INFO L225 Difference]: With dead ends: 267 [2025-03-08 05:11:53,579 INFO L226 Difference]: Without dead ends: 215 [2025-03-08 05:11:53,580 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 155 GetRequests, 140 SyntacticMatches, 2 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 40 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=48, Invalid=162, Unknown=0, NotChecked=0, Total=210 [2025-03-08 05:11:53,580 INFO L435 NwaCegarLoop]: 41 mSDtfsCounter, 16 mSDsluCounter, 194 mSDsCounter, 0 mSdLazyCounter, 125 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 235 SdHoareTripleChecker+Invalid, 136 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 125 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:11:53,580 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 235 Invalid, 136 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 125 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:11:53,581 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 215 states. [2025-03-08 05:11:53,613 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 215 to 210. [2025-03-08 05:11:53,614 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 210 states, 144 states have (on average 1.1527777777777777) internal successors, (166), 147 states have internal predecessors, (166), 40 states have call successors, (40), 25 states have call predecessors, (40), 25 states have return successors, (39), 37 states have call predecessors, (39), 39 states have call successors, (39) [2025-03-08 05:11:53,615 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 210 states to 210 states and 245 transitions. [2025-03-08 05:11:53,615 INFO L78 Accepts]: Start accepts. Automaton has 210 states and 245 transitions. Word has length 74 [2025-03-08 05:11:53,615 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:11:53,615 INFO L471 AbstractCegarLoop]: Abstraction has 210 states and 245 transitions. [2025-03-08 05:11:53,615 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 3.923076923076923) internal successors, (51), 11 states have internal predecessors, (51), 7 states have call successors, (35), 3 states have call predecessors, (35), 1 states have return successors, (32), 7 states have call predecessors, (32), 7 states have call successors, (32) [2025-03-08 05:11:53,615 INFO L276 IsEmpty]: Start isEmpty. Operand 210 states and 245 transitions. [2025-03-08 05:11:53,616 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2025-03-08 05:11:53,616 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:11:53,616 INFO L218 NwaCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2025-03-08 05:11:53,622 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-08 05:11:53,820 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,SelfDestructingSolverStorable11 [2025-03-08 05:11:53,820 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:11:53,820 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:11:53,820 INFO L85 PathProgramCache]: Analyzing trace with hash 808388229, now seen corresponding path program 2 times [2025-03-08 05:11:53,820 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:11:53,820 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1985735959] [2025-03-08 05:11:53,821 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 05:11:53,821 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:11:53,825 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 90 statements into 2 equivalence classes. [2025-03-08 05:11:53,844 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 90 of 90 statements. [2025-03-08 05:11:53,844 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 05:11:53,844 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:11:53,845 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1304136834] [2025-03-08 05:11:53,845 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 05:11:53,845 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:11:53,845 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:11:53,847 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-08 05:11:53,848 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-08 05:11:53,870 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 90 statements into 2 equivalence classes. [2025-03-08 05:11:53,890 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 90 of 90 statements. [2025-03-08 05:11:53,890 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 05:11:53,890 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:11:53,891 INFO L256 TraceCheckSpWp]: Trace formula consists of 238 conjuncts, 48 conjuncts are in the unsatisfiable core [2025-03-08 05:11:53,894 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:11:54,293 INFO L134 CoverageAnalysis]: Checked inductivity of 368 backedges. 28 proven. 64 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2025-03-08 05:11:54,293 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:12:06,912 INFO L134 CoverageAnalysis]: Checked inductivity of 368 backedges. 28 proven. 64 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2025-03-08 05:12:06,913 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:12:06,913 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1985735959] [2025-03-08 05:12:06,913 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:12:06,913 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1304136834] [2025-03-08 05:12:06,913 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1304136834] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:12:06,913 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-08 05:12:06,913 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 25 [2025-03-08 05:12:06,913 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2007958870] [2025-03-08 05:12:06,913 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-08 05:12:06,914 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2025-03-08 05:12:06,914 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:12:06,915 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2025-03-08 05:12:06,915 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=107, Invalid=493, Unknown=0, NotChecked=0, Total=600 [2025-03-08 05:12:06,915 INFO L87 Difference]: Start difference. First operand 210 states and 245 transitions. Second operand has 25 states, 25 states have (on average 2.16) internal successors, (54), 23 states have internal predecessors, (54), 13 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 11 states have call predecessors, (26), 11 states have call successors, (26) [2025-03-08 05:12:14,337 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:12:14,337 INFO L93 Difference]: Finished difference Result 319 states and 404 transitions. [2025-03-08 05:12:14,338 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2025-03-08 05:12:14,338 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 25 states have (on average 2.16) internal successors, (54), 23 states have internal predecessors, (54), 13 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 11 states have call predecessors, (26), 11 states have call successors, (26) Word has length 90 [2025-03-08 05:12:14,338 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:12:14,339 INFO L225 Difference]: With dead ends: 319 [2025-03-08 05:12:14,339 INFO L226 Difference]: Without dead ends: 283 [2025-03-08 05:12:14,340 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 195 GetRequests, 155 SyntacticMatches, 0 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 240 ImplicationChecksByTransitivity, 8.1s TimeCoverageRelationStatistics Valid=359, Invalid=1363, Unknown=0, NotChecked=0, Total=1722 [2025-03-08 05:12:14,340 INFO L435 NwaCegarLoop]: 57 mSDtfsCounter, 68 mSDsluCounter, 641 mSDsCounter, 0 mSdLazyCounter, 719 mSolverCounterSat, 150 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 70 SdHoareTripleChecker+Valid, 698 SdHoareTripleChecker+Invalid, 869 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 150 IncrementalHoareTripleChecker+Valid, 719 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.2s IncrementalHoareTripleChecker+Time [2025-03-08 05:12:14,341 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [70 Valid, 698 Invalid, 869 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [150 Valid, 719 Invalid, 0 Unknown, 0 Unchecked, 1.2s Time] [2025-03-08 05:12:14,341 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 283 states. [2025-03-08 05:12:14,381 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 283 to 245. [2025-03-08 05:12:14,382 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 245 states, 167 states have (on average 1.1736526946107784) internal successors, (196), 171 states have internal predecessors, (196), 49 states have call successors, (49), 28 states have call predecessors, (49), 28 states have return successors, (48), 45 states have call predecessors, (48), 48 states have call successors, (48) [2025-03-08 05:12:14,383 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 245 states to 245 states and 293 transitions. [2025-03-08 05:12:14,383 INFO L78 Accepts]: Start accepts. Automaton has 245 states and 293 transitions. Word has length 90 [2025-03-08 05:12:14,383 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:12:14,383 INFO L471 AbstractCegarLoop]: Abstraction has 245 states and 293 transitions. [2025-03-08 05:12:14,384 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 25 states have (on average 2.16) internal successors, (54), 23 states have internal predecessors, (54), 13 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 11 states have call predecessors, (26), 11 states have call successors, (26) [2025-03-08 05:12:14,384 INFO L276 IsEmpty]: Start isEmpty. Operand 245 states and 293 transitions. [2025-03-08 05:12:14,384 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 96 [2025-03-08 05:12:14,384 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:12:14,384 INFO L218 NwaCegarLoop]: trace histogram [15, 14, 14, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2025-03-08 05:12:14,390 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-08 05:12:14,586 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2025-03-08 05:12:14,586 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:12:14,586 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:12:14,586 INFO L85 PathProgramCache]: Analyzing trace with hash -210626755, now seen corresponding path program 3 times [2025-03-08 05:12:14,586 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:12:14,586 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1408896390] [2025-03-08 05:12:14,586 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-08 05:12:14,586 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:12:14,592 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 95 statements into 9 equivalence classes. [2025-03-08 05:12:14,627 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 9 check-sat command(s) and asserted 95 of 95 statements. [2025-03-08 05:12:14,627 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 9 check-sat command(s) [2025-03-08 05:12:14,627 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:12:14,629 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [89032138] [2025-03-08 05:12:14,629 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-08 05:12:14,629 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:12:14,629 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:12:14,631 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-08 05:12:14,632 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-08 05:12:14,656 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 95 statements into 9 equivalence classes. [2025-03-08 05:12:14,672 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) and asserted 58 of 95 statements. [2025-03-08 05:12:14,672 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2025-03-08 05:12:14,672 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:12:14,673 INFO L256 TraceCheckSpWp]: Trace formula consists of 172 conjuncts, 26 conjuncts are in the unsatisfiable core [2025-03-08 05:12:14,675 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:12:14,772 INFO L134 CoverageAnalysis]: Checked inductivity of 424 backedges. 81 proven. 41 refuted. 0 times theorem prover too weak. 302 trivial. 0 not checked. [2025-03-08 05:12:14,772 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:12:16,529 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:12:16,530 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1408896390] [2025-03-08 05:12:16,530 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:12:16,530 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [89032138] [2025-03-08 05:12:16,530 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [89032138] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:12:16,530 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-08 05:12:16,530 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2025-03-08 05:12:16,530 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [844930851] [2025-03-08 05:12:16,530 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-08 05:12:16,530 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-03-08 05:12:16,530 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:12:16,530 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-08 05:12:16,530 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=32, Invalid=124, Unknown=0, NotChecked=0, Total=156 [2025-03-08 05:12:16,531 INFO L87 Difference]: Start difference. First operand 245 states and 293 transitions. Second operand has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2025-03-08 05:12:16,651 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:12:16,652 INFO L93 Difference]: Finished difference Result 268 states and 314 transitions. [2025-03-08 05:12:16,652 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-03-08 05:12:16,652 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) Word has length 95 [2025-03-08 05:12:16,652 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:12:16,653 INFO L225 Difference]: With dead ends: 268 [2025-03-08 05:12:16,653 INFO L226 Difference]: Without dead ends: 266 [2025-03-08 05:12:16,654 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 110 GetRequests, 97 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=47, Invalid=163, Unknown=0, NotChecked=0, Total=210 [2025-03-08 05:12:16,654 INFO L435 NwaCegarLoop]: 22 mSDtfsCounter, 19 mSDsluCounter, 85 mSDsCounter, 0 mSdLazyCounter, 126 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 107 SdHoareTripleChecker+Invalid, 136 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 126 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:12:16,654 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 107 Invalid, 136 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 126 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:12:16,654 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 266 states. [2025-03-08 05:12:16,693 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 266 to 261. [2025-03-08 05:12:16,694 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 261 states, 179 states have (on average 1.1620111731843576) internal successors, (208), 183 states have internal predecessors, (208), 49 states have call successors, (49), 32 states have call predecessors, (49), 32 states have return successors, (48), 45 states have call predecessors, (48), 48 states have call successors, (48) [2025-03-08 05:12:16,695 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 261 states to 261 states and 305 transitions. [2025-03-08 05:12:16,695 INFO L78 Accepts]: Start accepts. Automaton has 261 states and 305 transitions. Word has length 95 [2025-03-08 05:12:16,695 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:12:16,695 INFO L471 AbstractCegarLoop]: Abstraction has 261 states and 305 transitions. [2025-03-08 05:12:16,695 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2025-03-08 05:12:16,695 INFO L276 IsEmpty]: Start isEmpty. Operand 261 states and 305 transitions. [2025-03-08 05:12:16,696 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2025-03-08 05:12:16,696 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:12:16,696 INFO L218 NwaCegarLoop]: trace histogram [15, 14, 14, 5, 4, 4, 4, 4, 4, 4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:12:16,703 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2025-03-08 05:12:16,900 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,SelfDestructingSolverStorable13 [2025-03-08 05:12:16,900 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:12:16,900 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:12:16,900 INFO L85 PathProgramCache]: Analyzing trace with hash 1481633006, now seen corresponding path program 1 times [2025-03-08 05:12:16,900 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:12:16,900 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [343497019] [2025-03-08 05:12:16,900 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:12:16,900 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:12:16,903 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 96 statements into 1 equivalence classes. [2025-03-08 05:12:16,908 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 96 of 96 statements. [2025-03-08 05:12:16,909 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:12:16,909 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:12:17,012 INFO L134 CoverageAnalysis]: Checked inductivity of 438 backedges. 28 proven. 44 refuted. 0 times theorem prover too weak. 366 trivial. 0 not checked. [2025-03-08 05:12:17,012 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:12:17,012 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [343497019] [2025-03-08 05:12:17,012 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [343497019] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:12:17,012 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1911831261] [2025-03-08 05:12:17,012 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:12:17,012 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:12:17,012 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:12:17,014 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-08 05:12:17,016 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-08 05:12:17,035 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 96 statements into 1 equivalence classes. [2025-03-08 05:12:17,054 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 96 of 96 statements. [2025-03-08 05:12:17,054 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:12:17,054 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:12:17,055 INFO L256 TraceCheckSpWp]: Trace formula consists of 251 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-08 05:12:17,056 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:12:17,129 INFO L134 CoverageAnalysis]: Checked inductivity of 438 backedges. 120 proven. 260 refuted. 0 times theorem prover too weak. 58 trivial. 0 not checked. [2025-03-08 05:12:17,129 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:12:17,231 INFO L134 CoverageAnalysis]: Checked inductivity of 438 backedges. 28 proven. 44 refuted. 0 times theorem prover too weak. 366 trivial. 0 not checked. [2025-03-08 05:12:17,232 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1911831261] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:12:17,232 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 05:12:17,232 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7, 8] total 14 [2025-03-08 05:12:17,232 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2082727712] [2025-03-08 05:12:17,232 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 05:12:17,232 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2025-03-08 05:12:17,232 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:12:17,233 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2025-03-08 05:12:17,233 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2025-03-08 05:12:17,233 INFO L87 Difference]: Start difference. First operand 261 states and 305 transitions. Second operand has 14 states, 14 states have (on average 4.071428571428571) internal successors, (57), 14 states have internal predecessors, (57), 9 states have call successors, (41), 6 states have call predecessors, (41), 6 states have return successors, (40), 9 states have call predecessors, (40), 9 states have call successors, (40) [2025-03-08 05:12:17,565 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:12:17,565 INFO L93 Difference]: Finished difference Result 720 states and 884 transitions. [2025-03-08 05:12:17,566 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2025-03-08 05:12:17,566 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 4.071428571428571) internal successors, (57), 14 states have internal predecessors, (57), 9 states have call successors, (41), 6 states have call predecessors, (41), 6 states have return successors, (40), 9 states have call predecessors, (40), 9 states have call successors, (40) Word has length 96 [2025-03-08 05:12:17,566 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:12:17,568 INFO L225 Difference]: With dead ends: 720 [2025-03-08 05:12:17,568 INFO L226 Difference]: Without dead ends: 650 [2025-03-08 05:12:17,569 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 207 GetRequests, 186 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 55 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=184, Invalid=322, Unknown=0, NotChecked=0, Total=506 [2025-03-08 05:12:17,569 INFO L435 NwaCegarLoop]: 29 mSDtfsCounter, 156 mSDsluCounter, 180 mSDsCounter, 0 mSdLazyCounter, 144 mSolverCounterSat, 44 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 156 SdHoareTripleChecker+Valid, 209 SdHoareTripleChecker+Invalid, 188 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 44 IncrementalHoareTripleChecker+Valid, 144 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:12:17,569 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [156 Valid, 209 Invalid, 188 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [44 Valid, 144 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:12:17,570 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 650 states. [2025-03-08 05:12:17,678 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 650 to 562. [2025-03-08 05:12:17,679 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 562 states, 376 states have (on average 1.2074468085106382) internal successors, (454), 394 states have internal predecessors, (454), 116 states have call successors, (116), 69 states have call predecessors, (116), 69 states have return successors, (112), 98 states have call predecessors, (112), 112 states have call successors, (112) [2025-03-08 05:12:17,681 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 562 states to 562 states and 682 transitions. [2025-03-08 05:12:17,682 INFO L78 Accepts]: Start accepts. Automaton has 562 states and 682 transitions. Word has length 96 [2025-03-08 05:12:17,682 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:12:17,682 INFO L471 AbstractCegarLoop]: Abstraction has 562 states and 682 transitions. [2025-03-08 05:12:17,682 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 4.071428571428571) internal successors, (57), 14 states have internal predecessors, (57), 9 states have call successors, (41), 6 states have call predecessors, (41), 6 states have return successors, (40), 9 states have call predecessors, (40), 9 states have call successors, (40) [2025-03-08 05:12:17,682 INFO L276 IsEmpty]: Start isEmpty. Operand 562 states and 682 transitions. [2025-03-08 05:12:17,683 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2025-03-08 05:12:17,683 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:12:17,683 INFO L218 NwaCegarLoop]: trace histogram [16, 15, 15, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:12:17,689 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-08 05:12:17,883 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,SelfDestructingSolverStorable14 [2025-03-08 05:12:17,883 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:12:17,884 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:12:17,884 INFO L85 PathProgramCache]: Analyzing trace with hash -473327751, now seen corresponding path program 2 times [2025-03-08 05:12:17,884 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:12:17,884 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [88411104] [2025-03-08 05:12:17,884 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 05:12:17,884 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:12:17,887 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 101 statements into 2 equivalence classes. [2025-03-08 05:12:17,904 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 101 of 101 statements. [2025-03-08 05:12:17,907 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 05:12:17,907 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:12:17,908 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [636450502] [2025-03-08 05:12:17,908 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 05:12:17,908 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:12:17,908 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:12:17,910 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-08 05:12:17,911 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-08 05:12:17,935 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 101 statements into 2 equivalence classes. [2025-03-08 05:12:17,958 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 101 of 101 statements. [2025-03-08 05:12:17,958 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 05:12:17,958 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:12:17,960 INFO L256 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 53 conjuncts are in the unsatisfiable core [2025-03-08 05:12:17,962 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:12:18,261 INFO L134 CoverageAnalysis]: Checked inductivity of 484 backedges. 32 proven. 74 refuted. 0 times theorem prover too weak. 378 trivial. 0 not checked. [2025-03-08 05:12:18,261 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:12:19,970 INFO L134 CoverageAnalysis]: Checked inductivity of 484 backedges. 32 proven. 74 refuted. 0 times theorem prover too weak. 378 trivial. 0 not checked. [2025-03-08 05:12:19,970 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:12:19,970 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [88411104] [2025-03-08 05:12:19,970 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:12:19,970 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [636450502] [2025-03-08 05:12:19,970 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [636450502] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:12:19,970 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-08 05:12:19,970 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15] total 27 [2025-03-08 05:12:19,970 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1412831309] [2025-03-08 05:12:19,970 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-08 05:12:19,971 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2025-03-08 05:12:19,971 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:12:19,971 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2025-03-08 05:12:19,971 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=157, Invalid=545, Unknown=0, NotChecked=0, Total=702 [2025-03-08 05:12:19,971 INFO L87 Difference]: Start difference. First operand 562 states and 682 transitions. Second operand has 27 states, 25 states have (on average 2.24) internal successors, (56), 25 states have internal predecessors, (56), 15 states have call successors, (32), 3 states have call predecessors, (32), 2 states have return successors, (30), 13 states have call predecessors, (30), 13 states have call successors, (30) [2025-03-08 05:12:23,565 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:12:23,565 INFO L93 Difference]: Finished difference Result 710 states and 871 transitions. [2025-03-08 05:12:23,566 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2025-03-08 05:12:23,566 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 25 states have (on average 2.24) internal successors, (56), 25 states have internal predecessors, (56), 15 states have call successors, (32), 3 states have call predecessors, (32), 2 states have return successors, (30), 13 states have call predecessors, (30), 13 states have call successors, (30) Word has length 101 [2025-03-08 05:12:23,566 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:12:23,569 INFO L225 Difference]: With dead ends: 710 [2025-03-08 05:12:23,569 INFO L226 Difference]: Without dead ends: 625 [2025-03-08 05:12:23,569 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 210 GetRequests, 175 SyntacticMatches, 0 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 204 ImplicationChecksByTransitivity, 2.7s TimeCoverageRelationStatistics Valid=333, Invalid=999, Unknown=0, NotChecked=0, Total=1332 [2025-03-08 05:12:23,571 INFO L435 NwaCegarLoop]: 55 mSDtfsCounter, 88 mSDsluCounter, 527 mSDsCounter, 0 mSdLazyCounter, 600 mSolverCounterSat, 109 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 96 SdHoareTripleChecker+Valid, 582 SdHoareTripleChecker+Invalid, 709 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 109 IncrementalHoareTripleChecker+Valid, 600 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.3s IncrementalHoareTripleChecker+Time [2025-03-08 05:12:23,571 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [96 Valid, 582 Invalid, 709 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [109 Valid, 600 Invalid, 0 Unknown, 0 Unchecked, 1.3s Time] [2025-03-08 05:12:23,572 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 625 states. [2025-03-08 05:12:23,727 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 625 to 554. [2025-03-08 05:12:23,729 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 554 states, 372 states have (on average 1.1935483870967742) internal successors, (444), 387 states have internal predecessors, (444), 111 states have call successors, (111), 71 states have call predecessors, (111), 70 states have return successors, (107), 95 states have call predecessors, (107), 107 states have call successors, (107) [2025-03-08 05:12:23,730 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 554 states to 554 states and 662 transitions. [2025-03-08 05:12:23,731 INFO L78 Accepts]: Start accepts. Automaton has 554 states and 662 transitions. Word has length 101 [2025-03-08 05:12:23,731 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:12:23,731 INFO L471 AbstractCegarLoop]: Abstraction has 554 states and 662 transitions. [2025-03-08 05:12:23,731 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 25 states have (on average 2.24) internal successors, (56), 25 states have internal predecessors, (56), 15 states have call successors, (32), 3 states have call predecessors, (32), 2 states have return successors, (30), 13 states have call predecessors, (30), 13 states have call successors, (30) [2025-03-08 05:12:23,731 INFO L276 IsEmpty]: Start isEmpty. Operand 554 states and 662 transitions. [2025-03-08 05:12:23,733 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 105 [2025-03-08 05:12:23,733 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:12:23,734 INFO L218 NwaCegarLoop]: trace histogram [16, 15, 15, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:12:23,740 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2025-03-08 05:12:23,938 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,SelfDestructingSolverStorable15 [2025-03-08 05:12:23,938 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:12:23,938 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:12:23,938 INFO L85 PathProgramCache]: Analyzing trace with hash -313503776, now seen corresponding path program 1 times [2025-03-08 05:12:23,938 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:12:23,938 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1891960996] [2025-03-08 05:12:23,938 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:12:23,938 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:12:23,945 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 104 statements into 1 equivalence classes. [2025-03-08 05:12:23,957 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 104 of 104 statements. [2025-03-08 05:12:23,957 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:12:23,957 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:12:24,089 INFO L134 CoverageAnalysis]: Checked inductivity of 492 backedges. 30 proven. 42 refuted. 0 times theorem prover too weak. 420 trivial. 0 not checked. [2025-03-08 05:12:24,089 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:12:24,089 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1891960996] [2025-03-08 05:12:24,089 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1891960996] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:12:24,089 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [385098384] [2025-03-08 05:12:24,089 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:12:24,089 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:12:24,089 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:12:24,091 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-08 05:12:24,093 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-08 05:12:24,115 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 104 statements into 1 equivalence classes. [2025-03-08 05:12:24,135 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 104 of 104 statements. [2025-03-08 05:12:24,136 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:12:24,136 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:12:24,138 INFO L256 TraceCheckSpWp]: Trace formula consists of 267 conjuncts, 15 conjuncts are in the unsatisfiable core [2025-03-08 05:12:24,140 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:12:24,217 INFO L134 CoverageAnalysis]: Checked inductivity of 492 backedges. 30 proven. 414 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2025-03-08 05:12:24,217 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:12:24,338 INFO L134 CoverageAnalysis]: Checked inductivity of 492 backedges. 30 proven. 42 refuted. 0 times theorem prover too weak. 420 trivial. 0 not checked. [2025-03-08 05:12:24,338 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [385098384] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:12:24,338 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 05:12:24,339 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9, 10] total 14 [2025-03-08 05:12:24,339 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1928230807] [2025-03-08 05:12:24,339 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 05:12:24,339 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2025-03-08 05:12:24,339 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:12:24,339 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2025-03-08 05:12:24,340 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2025-03-08 05:12:24,340 INFO L87 Difference]: Start difference. First operand 554 states and 662 transitions. Second operand has 14 states, 14 states have (on average 5.285714285714286) internal successors, (74), 14 states have internal predecessors, (74), 10 states have call successors, (46), 8 states have call predecessors, (46), 7 states have return successors, (45), 9 states have call predecessors, (45), 9 states have call successors, (45) [2025-03-08 05:12:24,675 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:12:24,675 INFO L93 Difference]: Finished difference Result 681 states and 819 transitions. [2025-03-08 05:12:24,676 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2025-03-08 05:12:24,676 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 5.285714285714286) internal successors, (74), 14 states have internal predecessors, (74), 10 states have call successors, (46), 8 states have call predecessors, (46), 7 states have return successors, (45), 9 states have call predecessors, (45), 9 states have call successors, (45) Word has length 104 [2025-03-08 05:12:24,676 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:12:24,679 INFO L225 Difference]: With dead ends: 681 [2025-03-08 05:12:24,679 INFO L226 Difference]: Without dead ends: 646 [2025-03-08 05:12:24,680 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 222 GetRequests, 200 SyntacticMatches, 4 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 49 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=129, Invalid=251, Unknown=0, NotChecked=0, Total=380 [2025-03-08 05:12:24,680 INFO L435 NwaCegarLoop]: 29 mSDtfsCounter, 118 mSDsluCounter, 171 mSDsCounter, 0 mSdLazyCounter, 136 mSolverCounterSat, 54 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 118 SdHoareTripleChecker+Valid, 200 SdHoareTripleChecker+Invalid, 190 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 54 IncrementalHoareTripleChecker+Valid, 136 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:12:24,681 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [118 Valid, 200 Invalid, 190 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [54 Valid, 136 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:12:24,681 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 646 states. [2025-03-08 05:12:24,853 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 646 to 638. [2025-03-08 05:12:24,853 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 638 states, 435 states have (on average 1.1517241379310346) internal successors, (501), 449 states have internal predecessors, (501), 125 states have call successors, (125), 78 states have call predecessors, (125), 77 states have return successors, (120), 110 states have call predecessors, (120), 120 states have call successors, (120) [2025-03-08 05:12:24,855 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 638 states to 638 states and 746 transitions. [2025-03-08 05:12:24,856 INFO L78 Accepts]: Start accepts. Automaton has 638 states and 746 transitions. Word has length 104 [2025-03-08 05:12:24,856 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:12:24,856 INFO L471 AbstractCegarLoop]: Abstraction has 638 states and 746 transitions. [2025-03-08 05:12:24,856 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 5.285714285714286) internal successors, (74), 14 states have internal predecessors, (74), 10 states have call successors, (46), 8 states have call predecessors, (46), 7 states have return successors, (45), 9 states have call predecessors, (45), 9 states have call successors, (45) [2025-03-08 05:12:24,856 INFO L276 IsEmpty]: Start isEmpty. Operand 638 states and 746 transitions. [2025-03-08 05:12:24,857 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 107 [2025-03-08 05:12:24,857 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:12:24,857 INFO L218 NwaCegarLoop]: trace histogram [17, 16, 16, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:12:24,863 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2025-03-08 05:12:25,057 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,SelfDestructingSolverStorable16 [2025-03-08 05:12:25,057 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:12:25,058 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:12:25,058 INFO L85 PathProgramCache]: Analyzing trace with hash -904540343, now seen corresponding path program 2 times [2025-03-08 05:12:25,058 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:12:25,058 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [123731143] [2025-03-08 05:12:25,058 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 05:12:25,058 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:12:25,061 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 106 statements into 2 equivalence classes. [2025-03-08 05:12:25,074 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 106 of 106 statements. [2025-03-08 05:12:25,077 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 05:12:25,077 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:12:25,313 INFO L134 CoverageAnalysis]: Checked inductivity of 546 backedges. 32 proven. 34 refuted. 0 times theorem prover too weak. 480 trivial. 0 not checked. [2025-03-08 05:12:25,315 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:12:25,315 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [123731143] [2025-03-08 05:12:25,315 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [123731143] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:12:25,315 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1952340674] [2025-03-08 05:12:25,315 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 05:12:25,315 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:12:25,315 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:12:25,318 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-08 05:12:25,320 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-08 05:12:25,344 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 106 statements into 2 equivalence classes. [2025-03-08 05:12:25,366 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 106 of 106 statements. [2025-03-08 05:12:25,366 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 05:12:25,366 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:12:25,368 INFO L256 TraceCheckSpWp]: Trace formula consists of 267 conjuncts, 45 conjuncts are in the unsatisfiable core [2025-03-08 05:12:25,370 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:12:25,615 INFO L134 CoverageAnalysis]: Checked inductivity of 546 backedges. 34 proven. 77 refuted. 0 times theorem prover too weak. 435 trivial. 0 not checked. [2025-03-08 05:12:25,615 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:12:26,359 INFO L134 CoverageAnalysis]: Checked inductivity of 546 backedges. 34 proven. 77 refuted. 0 times theorem prover too weak. 435 trivial. 0 not checked. [2025-03-08 05:12:26,359 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1952340674] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:12:26,359 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 05:12:26,359 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 14, 10] total 24 [2025-03-08 05:12:26,359 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2050554949] [2025-03-08 05:12:26,359 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 05:12:26,359 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2025-03-08 05:12:26,359 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:12:26,360 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2025-03-08 05:12:26,360 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=105, Invalid=447, Unknown=0, NotChecked=0, Total=552 [2025-03-08 05:12:26,360 INFO L87 Difference]: Start difference. First operand 638 states and 746 transitions. Second operand has 24 states, 24 states have (on average 3.2083333333333335) internal successors, (77), 23 states have internal predecessors, (77), 15 states have call successors, (49), 3 states have call predecessors, (49), 2 states have return successors, (47), 15 states have call predecessors, (47), 15 states have call successors, (47) [2025-03-08 05:12:26,857 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:12:26,857 INFO L93 Difference]: Finished difference Result 814 states and 967 transitions. [2025-03-08 05:12:26,858 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2025-03-08 05:12:26,858 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 24 states have (on average 3.2083333333333335) internal successors, (77), 23 states have internal predecessors, (77), 15 states have call successors, (49), 3 states have call predecessors, (49), 2 states have return successors, (47), 15 states have call predecessors, (47), 15 states have call successors, (47) Word has length 106 [2025-03-08 05:12:26,858 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:12:26,860 INFO L225 Difference]: With dead ends: 814 [2025-03-08 05:12:26,860 INFO L226 Difference]: Without dead ends: 546 [2025-03-08 05:12:26,861 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 222 GetRequests, 197 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 178 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=139, Invalid=563, Unknown=0, NotChecked=0, Total=702 [2025-03-08 05:12:26,861 INFO L435 NwaCegarLoop]: 46 mSDtfsCounter, 44 mSDsluCounter, 392 mSDsCounter, 0 mSdLazyCounter, 402 mSolverCounterSat, 34 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 53 SdHoareTripleChecker+Valid, 438 SdHoareTripleChecker+Invalid, 436 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 402 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-08 05:12:26,861 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [53 Valid, 438 Invalid, 436 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 402 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-08 05:12:26,862 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 546 states. [2025-03-08 05:12:26,988 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 546 to 491. [2025-03-08 05:12:26,989 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 491 states, 334 states have (on average 1.1287425149700598) internal successors, (377), 348 states have internal predecessors, (377), 97 states have call successors, (97), 59 states have call predecessors, (97), 59 states have return successors, (92), 83 states have call predecessors, (92), 92 states have call successors, (92) [2025-03-08 05:12:26,990 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 491 states to 491 states and 566 transitions. [2025-03-08 05:12:26,990 INFO L78 Accepts]: Start accepts. Automaton has 491 states and 566 transitions. Word has length 106 [2025-03-08 05:12:26,991 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:12:26,991 INFO L471 AbstractCegarLoop]: Abstraction has 491 states and 566 transitions. [2025-03-08 05:12:26,991 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 24 states have (on average 3.2083333333333335) internal successors, (77), 23 states have internal predecessors, (77), 15 states have call successors, (49), 3 states have call predecessors, (49), 2 states have return successors, (47), 15 states have call predecessors, (47), 15 states have call successors, (47) [2025-03-08 05:12:26,991 INFO L276 IsEmpty]: Start isEmpty. Operand 491 states and 566 transitions. [2025-03-08 05:12:26,992 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 109 [2025-03-08 05:12:26,992 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:12:26,992 INFO L218 NwaCegarLoop]: trace histogram [17, 16, 16, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2025-03-08 05:12:26,998 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2025-03-08 05:12:27,196 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable17,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:12:27,196 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:12:27,196 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:12:27,196 INFO L85 PathProgramCache]: Analyzing trace with hash -636794755, now seen corresponding path program 4 times [2025-03-08 05:12:27,196 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:12:27,196 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [205251606] [2025-03-08 05:12:27,196 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-08 05:12:27,197 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:12:27,200 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 108 statements into 2 equivalence classes. [2025-03-08 05:12:27,231 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 108 of 108 statements. [2025-03-08 05:12:27,231 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-08 05:12:27,231 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:12:27,232 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1267163096] [2025-03-08 05:12:27,232 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-08 05:12:27,232 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:12:27,233 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:12:27,234 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-08 05:12:27,236 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-08 05:12:27,258 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 108 statements into 2 equivalence classes. [2025-03-08 05:12:27,293 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 106 of 108 statements. [2025-03-08 05:12:27,293 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-03-08 05:12:27,293 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:12:27,294 INFO L256 TraceCheckSpWp]: Trace formula consists of 226 conjuncts, 68 conjuncts are in the unsatisfiable core [2025-03-08 05:12:27,296 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:12:42,088 INFO L134 CoverageAnalysis]: Checked inductivity of 560 backedges. 143 proven. 117 refuted. 0 times theorem prover too weak. 300 trivial. 0 not checked. [2025-03-08 05:12:42,088 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:12:55,078 WARN L286 SmtUtils]: Spent 8.01s on a formula simplification that was a NOOP. DAG size: 7 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify)