./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/array-patterns/array2_pattern.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/array-patterns/array2_pattern.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 1a25becec148beba97bef86c2a84619bb26dfafe7c127e8d70246837f0d2d470 --- Real Ultimate output --- This is Ultimate 0.3.0-?-e2fb8be-m [2025-03-08 00:39:25,651 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-08 00:39:25,705 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-08 00:39:25,709 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-08 00:39:25,709 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-08 00:39:25,735 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-08 00:39:25,736 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-08 00:39:25,736 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-08 00:39:25,737 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-08 00:39:25,737 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-08 00:39:25,738 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-08 00:39:25,738 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-08 00:39:25,738 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-08 00:39:25,738 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-08 00:39:25,738 INFO L153 SettingsManager]: * Use SBE=true [2025-03-08 00:39:25,738 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-08 00:39:25,739 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-08 00:39:25,739 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-08 00:39:25,739 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-08 00:39:25,739 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-08 00:39:25,739 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-08 00:39:25,739 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-08 00:39:25,739 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-08 00:39:25,739 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-08 00:39:25,739 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-08 00:39:25,739 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-08 00:39:25,740 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-08 00:39:25,740 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-08 00:39:25,740 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-08 00:39:25,740 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-08 00:39:25,740 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-08 00:39:25,740 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-08 00:39:25,740 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-08 00:39:25,741 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-08 00:39:25,741 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-08 00:39:25,741 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-08 00:39:25,741 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-08 00:39:25,741 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-08 00:39:25,741 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-08 00:39:25,741 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-08 00:39:25,741 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-08 00:39:25,741 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-08 00:39:25,741 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-08 00:39:25,741 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 -> 1a25becec148beba97bef86c2a84619bb26dfafe7c127e8d70246837f0d2d470 [2025-03-08 00:39:25,945 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-08 00:39:25,951 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-08 00:39:25,953 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-08 00:39:25,954 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-08 00:39:25,955 INFO L274 PluginConnector]: CDTParser initialized [2025-03-08 00:39:25,956 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/array-patterns/array2_pattern.c [2025-03-08 00:39:27,130 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3bdfd3a93/b24e594757a64513a7b8ed8187a0e024/FLAG8efdc4e5c [2025-03-08 00:39:27,329 INFO L384 CDTParser]: Found 1 translation units. [2025-03-08 00:39:27,337 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/array-patterns/array2_pattern.c [2025-03-08 00:39:27,346 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3bdfd3a93/b24e594757a64513a7b8ed8187a0e024/FLAG8efdc4e5c [2025-03-08 00:39:27,361 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3bdfd3a93/b24e594757a64513a7b8ed8187a0e024 [2025-03-08 00:39:27,363 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-08 00:39:27,364 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-08 00:39:27,364 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-08 00:39:27,365 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-08 00:39:27,367 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-08 00:39:27,368 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.03 12:39:27" (1/1) ... [2025-03-08 00:39:27,368 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1e69d2ec and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 12:39:27, skipping insertion in model container [2025-03-08 00:39:27,368 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.03 12:39:27" (1/1) ... [2025-03-08 00:39:27,377 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-08 00:39:27,457 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/array-patterns/array2_pattern.c[1322,1335] [2025-03-08 00:39:27,468 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-08 00:39:27,474 INFO L200 MainTranslator]: Completed pre-run [2025-03-08 00:39:27,480 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/array-patterns/array2_pattern.c[1322,1335] [2025-03-08 00:39:27,486 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-08 00:39:27,494 INFO L204 MainTranslator]: Completed translation [2025-03-08 00:39:27,495 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 12:39:27 WrapperNode [2025-03-08 00:39:27,495 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-08 00:39:27,495 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-08 00:39:27,495 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-08 00:39:27,495 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-08 00:39:27,499 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 12:39:27" (1/1) ... [2025-03-08 00:39:27,503 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 12:39:27" (1/1) ... [2025-03-08 00:39:27,516 INFO L138 Inliner]: procedures = 16, calls = 24, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 73 [2025-03-08 00:39:27,516 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-08 00:39:27,517 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-08 00:39:27,517 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-08 00:39:27,517 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-08 00:39:27,523 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 12:39:27" (1/1) ... [2025-03-08 00:39:27,523 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 12:39:27" (1/1) ... [2025-03-08 00:39:27,526 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 12:39:27" (1/1) ... [2025-03-08 00:39:27,534 INFO L175 MemorySlicer]: Split 10 memory accesses to 3 slices as follows [2, 4, 4]. 40 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2, 0, 0]. The 4 writes are split as follows [0, 2, 2]. [2025-03-08 00:39:27,534 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 12:39:27" (1/1) ... [2025-03-08 00:39:27,534 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 12:39:27" (1/1) ... [2025-03-08 00:39:27,538 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 12:39:27" (1/1) ... [2025-03-08 00:39:27,539 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 12:39:27" (1/1) ... [2025-03-08 00:39:27,540 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 12:39:27" (1/1) ... [2025-03-08 00:39:27,543 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 12:39:27" (1/1) ... [2025-03-08 00:39:27,544 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-08 00:39:27,544 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-08 00:39:27,544 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-08 00:39:27,544 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-08 00:39:27,545 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 12:39:27" (1/1) ... [2025-03-08 00:39:27,549 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-08 00:39:27,556 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 00:39:27,566 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 00:39:27,568 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 00:39:27,583 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-08 00:39:27,583 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2025-03-08 00:39:27,583 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2025-03-08 00:39:27,583 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-08 00:39:27,583 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2025-03-08 00:39:27,583 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2025-03-08 00:39:27,583 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2025-03-08 00:39:27,584 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2025-03-08 00:39:27,584 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2025-03-08 00:39:27,584 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2025-03-08 00:39:27,584 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-08 00:39:27,584 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-08 00:39:27,584 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2025-03-08 00:39:27,584 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2025-03-08 00:39:27,584 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2025-03-08 00:39:27,584 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2025-03-08 00:39:27,632 INFO L256 CfgBuilder]: Building ICFG [2025-03-08 00:39:27,633 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-08 00:39:27,732 INFO L1307 $ProcedureCfgBuilder]: dead code at ProgramPoint L41: call ULTIMATE.dealloc(main_~#array1~0#1.base, main_~#array1~0#1.offset);havoc main_~#array1~0#1.base, main_~#array1~0#1.offset;call ULTIMATE.dealloc(main_~#array2~0#1.base, main_~#array2~0#1.offset);havoc main_~#array2~0#1.base, main_~#array2~0#1.offset; [2025-03-08 00:39:27,738 INFO L? ?]: Removed 12 outVars from TransFormulas that were not future-live. [2025-03-08 00:39:27,738 INFO L307 CfgBuilder]: Performing block encoding [2025-03-08 00:39:27,743 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-08 00:39:27,744 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-08 00:39:27,744 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 08.03 12:39:27 BoogieIcfgContainer [2025-03-08 00:39:27,744 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-08 00:39:27,746 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-08 00:39:27,746 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-08 00:39:27,748 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-08 00:39:27,749 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 08.03 12:39:27" (1/3) ... [2025-03-08 00:39:27,749 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@16c26938 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.03 12:39:27, skipping insertion in model container [2025-03-08 00:39:27,749 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 12:39:27" (2/3) ... [2025-03-08 00:39:27,749 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@16c26938 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.03 12:39:27, skipping insertion in model container [2025-03-08 00:39:27,749 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 08.03 12:39:27" (3/3) ... [2025-03-08 00:39:27,750 INFO L128 eAbstractionObserver]: Analyzing ICFG array2_pattern.c [2025-03-08 00:39:27,760 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-08 00:39:27,761 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG array2_pattern.c that has 2 procedures, 22 locations, 1 initial locations, 3 loop locations, and 1 error locations. [2025-03-08 00:39:27,797 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-08 00:39:27,807 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;@24d52dd1, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-08 00:39:27,807 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-08 00:39:27,810 INFO L276 IsEmpty]: Start isEmpty. Operand has 22 states, 17 states have (on average 1.411764705882353) internal successors, (24), 18 states have internal predecessors, (24), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-08 00:39:27,814 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2025-03-08 00:39:27,815 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:39:27,816 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 00:39:27,816 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:39:27,821 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:39:27,821 INFO L85 PathProgramCache]: Analyzing trace with hash -566993990, now seen corresponding path program 1 times [2025-03-08 00:39:27,826 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:39:27,827 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1783543029] [2025-03-08 00:39:27,827 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 00:39:27,827 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:39:27,871 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 14 statements into 1 equivalence classes. [2025-03-08 00:39:27,879 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 14 of 14 statements. [2025-03-08 00:39:27,880 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 00:39:27,880 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:39:27,910 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 00:39:27,911 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:39:27,911 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1783543029] [2025-03-08 00:39:27,911 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1783543029] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 00:39:27,912 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 00:39:27,912 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2025-03-08 00:39:27,913 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1680593569] [2025-03-08 00:39:27,913 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 00:39:27,915 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-03-08 00:39:27,915 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:39:27,926 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-03-08 00:39:27,927 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-08 00:39:27,928 INFO L87 Difference]: Start difference. First operand has 22 states, 17 states have (on average 1.411764705882353) internal successors, (24), 18 states have internal predecessors, (24), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Second operand has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-08 00:39:27,937 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:39:27,937 INFO L93 Difference]: Finished difference Result 41 states and 54 transitions. [2025-03-08 00:39:27,938 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-03-08 00:39:27,939 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 14 [2025-03-08 00:39:27,939 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:39:27,942 INFO L225 Difference]: With dead ends: 41 [2025-03-08 00:39:27,942 INFO L226 Difference]: Without dead ends: 18 [2025-03-08 00:39:27,944 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-08 00:39:27,946 INFO L435 NwaCegarLoop]: 25 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 25 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 00:39:27,946 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 00:39:27,955 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 18 states. [2025-03-08 00:39:27,963 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 18 to 18. [2025-03-08 00:39:27,963 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 18 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 14 states have internal predecessors, (17), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-08 00:39:27,965 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 18 states to 18 states and 21 transitions. [2025-03-08 00:39:27,966 INFO L78 Accepts]: Start accepts. Automaton has 18 states and 21 transitions. Word has length 14 [2025-03-08 00:39:27,967 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:39:27,967 INFO L471 AbstractCegarLoop]: Abstraction has 18 states and 21 transitions. [2025-03-08 00:39:27,967 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-08 00:39:27,967 INFO L276 IsEmpty]: Start isEmpty. Operand 18 states and 21 transitions. [2025-03-08 00:39:27,968 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2025-03-08 00:39:27,968 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:39:27,968 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 00:39:27,968 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-03-08 00:39:27,968 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:39:27,969 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:39:27,969 INFO L85 PathProgramCache]: Analyzing trace with hash 1555530677, now seen corresponding path program 1 times [2025-03-08 00:39:27,969 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:39:27,969 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1535887068] [2025-03-08 00:39:27,969 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 00:39:27,969 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:39:27,983 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-03-08 00:39:28,017 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-03-08 00:39:28,017 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 00:39:28,017 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:39:28,159 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-08 00:39:28,159 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:39:28,160 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1535887068] [2025-03-08 00:39:28,160 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1535887068] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 00:39:28,160 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 00:39:28,160 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-03-08 00:39:28,160 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [235932099] [2025-03-08 00:39:28,160 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 00:39:28,161 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2025-03-08 00:39:28,161 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:39:28,161 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2025-03-08 00:39:28,161 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-08 00:39:28,162 INFO L87 Difference]: Start difference. First operand 18 states and 21 transitions. Second operand has 4 states, 4 states have (on average 3.5) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-08 00:39:28,175 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:39:28,175 INFO L93 Difference]: Finished difference Result 22 states and 25 transitions. [2025-03-08 00:39:28,176 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2025-03-08 00:39:28,176 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 3.5) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 21 [2025-03-08 00:39:28,176 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:39:28,176 INFO L225 Difference]: With dead ends: 22 [2025-03-08 00:39:28,177 INFO L226 Difference]: Without dead ends: 19 [2025-03-08 00:39:28,177 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 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 00:39:28,177 INFO L435 NwaCegarLoop]: 19 mSDtfsCounter, 2 mSDsluCounter, 27 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 46 SdHoareTripleChecker+Invalid, 8 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 8 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 00:39:28,178 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 46 Invalid, 8 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 8 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 00:39:28,178 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states. [2025-03-08 00:39:28,180 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 19. [2025-03-08 00:39:28,181 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 19 states, 15 states have (on average 1.2) internal successors, (18), 15 states have internal predecessors, (18), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-08 00:39:28,181 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 22 transitions. [2025-03-08 00:39:28,181 INFO L78 Accepts]: Start accepts. Automaton has 19 states and 22 transitions. Word has length 21 [2025-03-08 00:39:28,182 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:39:28,182 INFO L471 AbstractCegarLoop]: Abstraction has 19 states and 22 transitions. [2025-03-08 00:39:28,182 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 3.5) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-08 00:39:28,182 INFO L276 IsEmpty]: Start isEmpty. Operand 19 states and 22 transitions. [2025-03-08 00:39:28,183 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2025-03-08 00:39:28,183 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:39:28,183 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 00:39:28,184 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-03-08 00:39:28,184 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:39:28,185 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:39:28,185 INFO L85 PathProgramCache]: Analyzing trace with hash 976842484, now seen corresponding path program 1 times [2025-03-08 00:39:28,185 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:39:28,185 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [689240121] [2025-03-08 00:39:28,185 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 00:39:28,186 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:39:28,201 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 22 statements into 1 equivalence classes. [2025-03-08 00:39:28,219 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 22 of 22 statements. [2025-03-08 00:39:28,219 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 00:39:28,219 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:39:28,326 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-08 00:39:28,326 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:39:28,326 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [689240121] [2025-03-08 00:39:28,327 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [689240121] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 00:39:28,327 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 00:39:28,327 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-08 00:39:28,327 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1914934895] [2025-03-08 00:39:28,327 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 00:39:28,328 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-08 00:39:28,328 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:39:28,329 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-08 00:39:28,329 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2025-03-08 00:39:28,329 INFO L87 Difference]: Start difference. First operand 19 states and 22 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-08 00:39:28,372 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:39:28,373 INFO L93 Difference]: Finished difference Result 34 states and 39 transitions. [2025-03-08 00:39:28,373 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-08 00:39:28,374 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 22 [2025-03-08 00:39:28,374 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:39:28,374 INFO L225 Difference]: With dead ends: 34 [2025-03-08 00:39:28,374 INFO L226 Difference]: Without dead ends: 20 [2025-03-08 00:39:28,375 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2025-03-08 00:39:28,376 INFO L435 NwaCegarLoop]: 19 mSDtfsCounter, 5 mSDsluCounter, 25 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 44 SdHoareTripleChecker+Invalid, 24 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 22 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 00:39:28,376 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 44 Invalid, 24 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 00:39:28,377 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2025-03-08 00:39:28,380 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 20. [2025-03-08 00:39:28,380 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 16 states have (on average 1.1875) internal successors, (19), 16 states have internal predecessors, (19), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-08 00:39:28,381 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 23 transitions. [2025-03-08 00:39:28,381 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 23 transitions. Word has length 22 [2025-03-08 00:39:28,382 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:39:28,382 INFO L471 AbstractCegarLoop]: Abstraction has 20 states and 23 transitions. [2025-03-08 00:39:28,382 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-08 00:39:28,383 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 23 transitions. [2025-03-08 00:39:28,383 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2025-03-08 00:39:28,383 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:39:28,383 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 00:39:28,383 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2025-03-08 00:39:28,383 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:39:28,384 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:39:28,384 INFO L85 PathProgramCache]: Analyzing trace with hash -1516340531, now seen corresponding path program 1 times [2025-03-08 00:39:28,384 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:39:28,384 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [195382122] [2025-03-08 00:39:28,385 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 00:39:28,385 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:39:28,397 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 23 statements into 1 equivalence classes. [2025-03-08 00:39:28,419 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 23 of 23 statements. [2025-03-08 00:39:28,419 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 00:39:28,419 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 00:39:28,421 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1167575444] [2025-03-08 00:39:28,421 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 00:39:28,421 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:39:28,421 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 00:39:28,423 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 00:39:28,425 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 00:39:28,468 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 23 statements into 1 equivalence classes. [2025-03-08 00:39:28,494 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 23 of 23 statements. [2025-03-08 00:39:28,494 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 00:39:28,494 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:39:28,497 INFO L256 TraceCheckSpWp]: Trace formula consists of 112 conjuncts, 45 conjuncts are in the unsatisfiable core [2025-03-08 00:39:28,504 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 00:39:28,616 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-08 00:39:28,624 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-08 00:39:28,921 INFO L349 Elim1Store]: treesize reduction 25, result has 21.9 percent of original size [2025-03-08 00:39:28,922 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 21 [2025-03-08 00:39:28,944 INFO L349 Elim1Store]: treesize reduction 25, result has 21.9 percent of original size [2025-03-08 00:39:28,944 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 21 [2025-03-08 00:39:29,075 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 4 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-08 00:39:29,076 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 00:39:29,885 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:39:29,885 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [195382122] [2025-03-08 00:39:29,885 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 00:39:29,885 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1167575444] [2025-03-08 00:39:29,885 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1167575444] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 00:39:29,887 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-08 00:39:29,887 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2025-03-08 00:39:29,887 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [572247771] [2025-03-08 00:39:29,888 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-08 00:39:29,888 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-03-08 00:39:29,888 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:39:29,888 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-03-08 00:39:29,889 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=73, Invalid=347, Unknown=0, NotChecked=0, Total=420 [2025-03-08 00:39:29,889 INFO L87 Difference]: Start difference. First operand 20 states and 23 transitions. Second operand has 16 states, 16 states have (on average 1.1875) internal successors, (19), 13 states have internal predecessors, (19), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-08 00:39:30,259 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:39:30,259 INFO L93 Difference]: Finished difference Result 46 states and 51 transitions. [2025-03-08 00:39:30,260 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2025-03-08 00:39:30,260 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 1.1875) internal successors, (19), 13 states have internal predecessors, (19), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 23 [2025-03-08 00:39:30,260 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:39:30,260 INFO L225 Difference]: With dead ends: 46 [2025-03-08 00:39:30,260 INFO L226 Difference]: Without dead ends: 43 [2025-03-08 00:39:30,261 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 37 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 150 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=135, Invalid=621, Unknown=0, NotChecked=0, Total=756 [2025-03-08 00:39:30,261 INFO L435 NwaCegarLoop]: 16 mSDtfsCounter, 41 mSDsluCounter, 103 mSDsCounter, 0 mSdLazyCounter, 149 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 119 SdHoareTripleChecker+Invalid, 163 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 149 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-08 00:39:30,262 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [41 Valid, 119 Invalid, 163 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 149 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-08 00:39:30,262 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2025-03-08 00:39:30,266 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 35. [2025-03-08 00:39:30,267 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 28 states have (on average 1.1785714285714286) internal successors, (33), 28 states have internal predecessors, (33), 3 states have call successors, (3), 3 states have call predecessors, (3), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-03-08 00:39:30,267 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 39 transitions. [2025-03-08 00:39:30,267 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 39 transitions. Word has length 23 [2025-03-08 00:39:30,267 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:39:30,267 INFO L471 AbstractCegarLoop]: Abstraction has 35 states and 39 transitions. [2025-03-08 00:39:30,267 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 1.1875) internal successors, (19), 13 states have internal predecessors, (19), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-08 00:39:30,267 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 39 transitions. [2025-03-08 00:39:30,268 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2025-03-08 00:39:30,268 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:39:30,268 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 00:39:30,276 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2025-03-08 00:39:30,468 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 00:39:30,469 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:39:30,469 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:39:30,469 INFO L85 PathProgramCache]: Analyzing trace with hash -1495602668, now seen corresponding path program 2 times [2025-03-08 00:39:30,469 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:39:30,469 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [965077388] [2025-03-08 00:39:30,469 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 00:39:30,470 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:39:30,481 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 24 statements into 2 equivalence classes. [2025-03-08 00:39:30,497 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 24 of 24 statements. [2025-03-08 00:39:30,501 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 00:39:30,502 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:39:30,609 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-08 00:39:30,609 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:39:30,609 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [965077388] [2025-03-08 00:39:30,609 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [965077388] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 00:39:30,609 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [408453919] [2025-03-08 00:39:30,609 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 00:39:30,610 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:39:30,610 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 00:39:30,612 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 00:39:30,619 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 00:39:30,652 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 24 statements into 2 equivalence classes. [2025-03-08 00:39:30,668 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 24 of 24 statements. [2025-03-08 00:39:30,668 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 00:39:30,668 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:39:30,669 INFO L256 TraceCheckSpWp]: Trace formula consists of 123 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-03-08 00:39:30,670 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 00:39:30,714 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 5 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-08 00:39:30,714 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 00:39:30,761 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 1 proven. 3 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-08 00:39:30,761 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [408453919] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 00:39:30,762 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 00:39:30,762 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 11 [2025-03-08 00:39:30,762 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [378538463] [2025-03-08 00:39:30,762 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 00:39:30,762 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2025-03-08 00:39:30,762 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:39:30,763 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2025-03-08 00:39:30,763 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=75, Unknown=0, NotChecked=0, Total=110 [2025-03-08 00:39:30,763 INFO L87 Difference]: Start difference. First operand 35 states and 39 transitions. Second operand has 11 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 11 states have internal predecessors, (27), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-08 00:39:30,837 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:39:30,838 INFO L93 Difference]: Finished difference Result 40 states and 44 transitions. [2025-03-08 00:39:30,838 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-03-08 00:39:30,838 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 11 states have internal predecessors, (27), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 24 [2025-03-08 00:39:30,838 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:39:30,839 INFO L225 Difference]: With dead ends: 40 [2025-03-08 00:39:30,839 INFO L226 Difference]: Without dead ends: 37 [2025-03-08 00:39:30,839 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 55 GetRequests, 40 SyntacticMatches, 4 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 35 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=48, Invalid=108, Unknown=0, NotChecked=0, Total=156 [2025-03-08 00:39:30,840 INFO L435 NwaCegarLoop]: 25 mSDtfsCounter, 4 mSDsluCounter, 85 mSDsCounter, 0 mSdLazyCounter, 106 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 110 SdHoareTripleChecker+Invalid, 113 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 106 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 00:39:30,840 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 110 Invalid, 113 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 106 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 00:39:30,840 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2025-03-08 00:39:30,843 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 25. [2025-03-08 00:39:30,843 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 25 states, 20 states have (on average 1.15) internal successors, (23), 20 states have internal predecessors, (23), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-08 00:39:30,844 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 27 transitions. [2025-03-08 00:39:30,844 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 27 transitions. Word has length 24 [2025-03-08 00:39:30,844 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:39:30,844 INFO L471 AbstractCegarLoop]: Abstraction has 25 states and 27 transitions. [2025-03-08 00:39:30,844 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 11 states have internal predecessors, (27), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-08 00:39:30,844 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 27 transitions. [2025-03-08 00:39:30,845 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2025-03-08 00:39:30,845 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:39:30,845 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 00:39:30,850 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2025-03-08 00:39:31,049 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 00:39:31,049 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:39:31,049 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:39:31,049 INFO L85 PathProgramCache]: Analyzing trace with hash 238115548, now seen corresponding path program 3 times [2025-03-08 00:39:31,049 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:39:31,049 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [291404400] [2025-03-08 00:39:31,050 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-08 00:39:31,050 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:39:31,055 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 24 statements into 3 equivalence classes. [2025-03-08 00:39:31,076 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) and asserted 24 of 24 statements. [2025-03-08 00:39:31,077 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2025-03-08 00:39:31,077 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:39:31,144 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-08 00:39:31,145 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:39:31,145 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [291404400] [2025-03-08 00:39:31,145 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [291404400] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 00:39:31,145 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1872369020] [2025-03-08 00:39:31,145 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-08 00:39:31,145 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:39:31,145 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 00:39:31,147 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 00:39:31,149 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 00:39:31,180 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 24 statements into 3 equivalence classes. [2025-03-08 00:39:31,195 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) and asserted 24 of 24 statements. [2025-03-08 00:39:31,195 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2025-03-08 00:39:31,195 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:39:31,196 INFO L256 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-03-08 00:39:31,197 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 00:39:31,234 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 7 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-08 00:39:31,234 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 00:39:31,265 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 3 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-08 00:39:31,265 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1872369020] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 00:39:31,266 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 00:39:31,266 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 11 [2025-03-08 00:39:31,266 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1037043003] [2025-03-08 00:39:31,266 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 00:39:31,266 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2025-03-08 00:39:31,266 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:39:31,267 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2025-03-08 00:39:31,267 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=75, Unknown=0, NotChecked=0, Total=110 [2025-03-08 00:39:31,267 INFO L87 Difference]: Start difference. First operand 25 states and 27 transitions. Second operand has 11 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 11 states have internal predecessors, (27), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-08 00:39:31,313 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:39:31,313 INFO L93 Difference]: Finished difference Result 41 states and 45 transitions. [2025-03-08 00:39:31,314 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-08 00:39:31,314 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 11 states have internal predecessors, (27), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 24 [2025-03-08 00:39:31,314 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:39:31,314 INFO L225 Difference]: With dead ends: 41 [2025-03-08 00:39:31,314 INFO L226 Difference]: Without dead ends: 26 [2025-03-08 00:39:31,315 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 41 SyntacticMatches, 3 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 39 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=43, Invalid=89, Unknown=0, NotChecked=0, Total=132 [2025-03-08 00:39:31,315 INFO L435 NwaCegarLoop]: 19 mSDtfsCounter, 1 mSDsluCounter, 37 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 56 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 37 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 00:39:31,315 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 56 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 00:39:31,315 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2025-03-08 00:39:31,320 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2025-03-08 00:39:31,320 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 21 states have (on average 1.1428571428571428) internal successors, (24), 21 states have internal predecessors, (24), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-08 00:39:31,322 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 28 transitions. [2025-03-08 00:39:31,322 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 28 transitions. Word has length 24 [2025-03-08 00:39:31,322 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:39:31,322 INFO L471 AbstractCegarLoop]: Abstraction has 26 states and 28 transitions. [2025-03-08 00:39:31,322 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 11 states have internal predecessors, (27), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-08 00:39:31,323 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 28 transitions. [2025-03-08 00:39:31,323 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2025-03-08 00:39:31,323 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:39:31,323 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 00:39:31,329 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2025-03-08 00:39:31,528 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 00:39:31,528 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:39:31,528 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:39:31,528 INFO L85 PathProgramCache]: Analyzing trace with hash 880989301, now seen corresponding path program 4 times [2025-03-08 00:39:31,528 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:39:31,528 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1500133495] [2025-03-08 00:39:31,528 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-08 00:39:31,529 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:39:31,539 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 25 statements into 2 equivalence classes. [2025-03-08 00:39:31,559 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 25 of 25 statements. [2025-03-08 00:39:31,560 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-08 00:39:31,560 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 00:39:31,561 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1627916668] [2025-03-08 00:39:31,561 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-08 00:39:31,561 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:39:31,561 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 00:39:31,562 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 00:39:31,564 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 00:39:31,599 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 25 statements into 2 equivalence classes. [2025-03-08 00:39:31,623 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 25 of 25 statements. [2025-03-08 00:39:31,624 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-08 00:39:31,624 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:39:31,630 INFO L256 TraceCheckSpWp]: Trace formula consists of 128 conjuncts, 45 conjuncts are in the unsatisfiable core [2025-03-08 00:39:31,635 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 00:39:31,676 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-08 00:39:31,681 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-08 00:39:31,715 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 18 [2025-03-08 00:39:31,725 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 18 [2025-03-08 00:39:32,058 INFO L349 Elim1Store]: treesize reduction 12, result has 60.0 percent of original size [2025-03-08 00:39:32,059 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 130 treesize of output 123 [2025-03-08 00:39:32,137 INFO L349 Elim1Store]: treesize reduction 133, result has 23.1 percent of original size [2025-03-08 00:39:32,138 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 5 select indices, 5 select index equivalence classes, 1 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 14 case distinctions, treesize of input 50 treesize of output 63 [2025-03-08 00:39:32,184 INFO L349 Elim1Store]: treesize reduction 94, result has 1.1 percent of original size [2025-03-08 00:39:32,184 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 4 select indices, 4 select index equivalence classes, 4 disjoint index pairs (out of 6 index pairs), introduced 6 new quantified variables, introduced 4 case distinctions, treesize of input 96 treesize of output 157 [2025-03-08 00:39:32,715 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:39:32,716 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 185 treesize of output 169 [2025-03-08 00:39:32,722 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 116 treesize of output 100 [2025-03-08 00:39:32,725 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-08 00:39:32,727 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-08 00:39:32,728 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-08 00:39:32,729 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-08 00:39:32,730 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-08 00:39:32,730 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 31 treesize of output 19 [2025-03-08 00:39:32,758 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 4 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-08 00:39:32,759 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 00:39:34,621 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:39:34,622 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1500133495] [2025-03-08 00:39:34,622 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 00:39:34,622 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1627916668] [2025-03-08 00:39:34,622 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1627916668] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 00:39:34,622 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-08 00:39:34,622 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2025-03-08 00:39:34,622 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [562505935] [2025-03-08 00:39:34,622 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-08 00:39:34,623 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2025-03-08 00:39:34,623 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:39:34,623 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2025-03-08 00:39:34,623 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=63, Invalid=317, Unknown=0, NotChecked=0, Total=380 [2025-03-08 00:39:34,623 INFO L87 Difference]: Start difference. First operand 26 states and 28 transitions. Second operand has 15 states, 15 states have (on average 1.4) internal successors, (21), 13 states have internal predecessors, (21), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-08 00:39:34,821 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:39:34,821 INFO L93 Difference]: Finished difference Result 46 states and 52 transitions. [2025-03-08 00:39:34,821 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2025-03-08 00:39:34,821 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 1.4) internal successors, (21), 13 states have internal predecessors, (21), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 25 [2025-03-08 00:39:34,822 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:39:34,822 INFO L225 Difference]: With dead ends: 46 [2025-03-08 00:39:34,822 INFO L226 Difference]: Without dead ends: 43 [2025-03-08 00:39:34,822 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 33 GetRequests, 14 SyntacticMatches, 1 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 82 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=63, Invalid=317, Unknown=0, NotChecked=0, Total=380 [2025-03-08 00:39:34,823 INFO L435 NwaCegarLoop]: 17 mSDtfsCounter, 15 mSDsluCounter, 116 mSDsCounter, 0 mSdLazyCounter, 151 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 133 SdHoareTripleChecker+Invalid, 153 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 151 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-08 00:39:34,823 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 133 Invalid, 153 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 151 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-08 00:39:34,823 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2025-03-08 00:39:34,829 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 37. [2025-03-08 00:39:34,829 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 30 states have (on average 1.1666666666666667) internal successors, (35), 30 states have internal predecessors, (35), 3 states have call successors, (3), 3 states have call predecessors, (3), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-03-08 00:39:34,829 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 41 transitions. [2025-03-08 00:39:34,830 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 41 transitions. Word has length 25 [2025-03-08 00:39:34,830 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:39:34,830 INFO L471 AbstractCegarLoop]: Abstraction has 37 states and 41 transitions. [2025-03-08 00:39:34,830 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 1.4) internal successors, (21), 13 states have internal predecessors, (21), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-08 00:39:34,830 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 41 transitions. [2025-03-08 00:39:34,830 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2025-03-08 00:39:34,831 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:39:34,831 INFO L218 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 00:39:34,837 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2025-03-08 00:39:35,035 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 00:39:35,035 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:39:35,035 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:39:35,035 INFO L85 PathProgramCache]: Analyzing trace with hash -664760836, now seen corresponding path program 5 times [2025-03-08 00:39:35,036 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:39:35,036 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [392797608] [2025-03-08 00:39:35,036 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-08 00:39:35,036 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:39:35,043 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 26 statements into 4 equivalence classes. [2025-03-08 00:39:35,052 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) and asserted 26 of 26 statements. [2025-03-08 00:39:35,052 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2025-03-08 00:39:35,052 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:39:35,148 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-08 00:39:35,149 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:39:35,149 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [392797608] [2025-03-08 00:39:35,149 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [392797608] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 00:39:35,149 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1932058836] [2025-03-08 00:39:35,149 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-08 00:39:35,149 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:39:35,149 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 00:39:35,152 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 00:39:35,154 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 00:39:35,190 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 26 statements into 4 equivalence classes. [2025-03-08 00:39:35,212 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) and asserted 26 of 26 statements. [2025-03-08 00:39:35,212 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2025-03-08 00:39:35,212 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:39:35,213 INFO L256 TraceCheckSpWp]: Trace formula consists of 139 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-08 00:39:35,214 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 00:39:35,266 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 7 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-08 00:39:35,266 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 00:39:35,312 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-08 00:39:35,312 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1932058836] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 00:39:35,312 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 00:39:35,312 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 12 [2025-03-08 00:39:35,312 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1649311944] [2025-03-08 00:39:35,312 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 00:39:35,312 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2025-03-08 00:39:35,312 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:39:35,313 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2025-03-08 00:39:35,313 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=93, Unknown=0, NotChecked=0, Total=132 [2025-03-08 00:39:35,313 INFO L87 Difference]: Start difference. First operand 37 states and 41 transitions. Second operand has 12 states, 12 states have (on average 2.1666666666666665) internal successors, (26), 12 states have internal predecessors, (26), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-08 00:39:35,402 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:39:35,403 INFO L93 Difference]: Finished difference Result 58 states and 63 transitions. [2025-03-08 00:39:35,403 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-03-08 00:39:35,403 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.1666666666666665) internal successors, (26), 12 states have internal predecessors, (26), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 26 [2025-03-08 00:39:35,403 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:39:35,404 INFO L225 Difference]: With dead ends: 58 [2025-03-08 00:39:35,404 INFO L226 Difference]: Without dead ends: 55 [2025-03-08 00:39:35,404 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 63 GetRequests, 42 SyntacticMatches, 7 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 70 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=73, Invalid=167, Unknown=0, NotChecked=0, Total=240 [2025-03-08 00:39:35,405 INFO L435 NwaCegarLoop]: 25 mSDtfsCounter, 4 mSDsluCounter, 83 mSDsCounter, 0 mSdLazyCounter, 92 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 108 SdHoareTripleChecker+Invalid, 96 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 92 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 00:39:35,405 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 108 Invalid, 96 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 92 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 00:39:35,405 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2025-03-08 00:39:35,418 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 45. [2025-03-08 00:39:35,418 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 36 states have (on average 1.1666666666666667) internal successors, (42), 36 states have internal predecessors, (42), 4 states have call successors, (4), 4 states have call predecessors, (4), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2025-03-08 00:39:35,418 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 50 transitions. [2025-03-08 00:39:35,419 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 50 transitions. Word has length 26 [2025-03-08 00:39:35,419 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:39:35,419 INFO L471 AbstractCegarLoop]: Abstraction has 45 states and 50 transitions. [2025-03-08 00:39:35,419 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 2.1666666666666665) internal successors, (26), 12 states have internal predecessors, (26), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-08 00:39:35,419 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 50 transitions. [2025-03-08 00:39:35,419 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2025-03-08 00:39:35,420 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:39:35,420 INFO L218 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 00:39:35,426 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2025-03-08 00:39:35,620 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:39:35,620 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:39:35,621 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:39:35,621 INFO L85 PathProgramCache]: Analyzing trace with hash 1540896308, now seen corresponding path program 6 times [2025-03-08 00:39:35,621 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:39:35,621 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [156248882] [2025-03-08 00:39:35,621 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-08 00:39:35,621 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:39:35,626 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 26 statements into 3 equivalence classes. [2025-03-08 00:39:35,640 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 3 check-sat command(s) and asserted 26 of 26 statements. [2025-03-08 00:39:35,642 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 3 check-sat command(s) [2025-03-08 00:39:35,642 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:39:35,727 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 4 proven. 5 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-08 00:39:35,727 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:39:35,727 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [156248882] [2025-03-08 00:39:35,727 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [156248882] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 00:39:35,727 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [370231714] [2025-03-08 00:39:35,728 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-08 00:39:35,728 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:39:35,728 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 00:39:35,730 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 00:39:35,731 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 00:39:35,762 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 26 statements into 3 equivalence classes. [2025-03-08 00:39:35,782 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 3 check-sat command(s) and asserted 26 of 26 statements. [2025-03-08 00:39:35,782 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 3 check-sat command(s) [2025-03-08 00:39:35,782 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:39:35,783 INFO L256 TraceCheckSpWp]: Trace formula consists of 133 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-08 00:39:35,784 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 00:39:35,823 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 10 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-08 00:39:35,823 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 00:39:35,865 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-08 00:39:35,865 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [370231714] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 00:39:35,865 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 00:39:35,865 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 13 [2025-03-08 00:39:35,865 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1241115075] [2025-03-08 00:39:35,865 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 00:39:35,865 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2025-03-08 00:39:35,866 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:39:35,866 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2025-03-08 00:39:35,866 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=109, Unknown=0, NotChecked=0, Total=156 [2025-03-08 00:39:35,866 INFO L87 Difference]: Start difference. First operand 45 states and 50 transitions. Second operand has 13 states, 13 states have (on average 2.1538461538461537) internal successors, (28), 13 states have internal predecessors, (28), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-08 00:39:35,954 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:39:35,955 INFO L93 Difference]: Finished difference Result 59 states and 64 transitions. [2025-03-08 00:39:35,955 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-08 00:39:35,956 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.1538461538461537) internal successors, (28), 13 states have internal predecessors, (28), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 26 [2025-03-08 00:39:35,956 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:39:35,956 INFO L225 Difference]: With dead ends: 59 [2025-03-08 00:39:35,956 INFO L226 Difference]: Without dead ends: 51 [2025-03-08 00:39:35,956 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 61 GetRequests, 43 SyntacticMatches, 5 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 63 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=66, Invalid=144, Unknown=0, NotChecked=0, Total=210 [2025-03-08 00:39:35,957 INFO L435 NwaCegarLoop]: 21 mSDtfsCounter, 4 mSDsluCounter, 111 mSDsCounter, 0 mSdLazyCounter, 113 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 132 SdHoareTripleChecker+Invalid, 122 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 113 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 00:39:35,957 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 132 Invalid, 122 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 113 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 00:39:35,957 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2025-03-08 00:39:35,964 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 48. [2025-03-08 00:39:35,964 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 39 states have (on average 1.1282051282051282) internal successors, (44), 39 states have internal predecessors, (44), 4 states have call successors, (4), 4 states have call predecessors, (4), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2025-03-08 00:39:35,964 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 52 transitions. [2025-03-08 00:39:35,965 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 52 transitions. Word has length 26 [2025-03-08 00:39:35,965 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:39:35,965 INFO L471 AbstractCegarLoop]: Abstraction has 48 states and 52 transitions. [2025-03-08 00:39:35,965 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.1538461538461537) internal successors, (28), 13 states have internal predecessors, (28), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-08 00:39:35,965 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 52 transitions. [2025-03-08 00:39:35,965 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2025-03-08 00:39:35,966 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:39:35,966 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 00:39:35,972 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2025-03-08 00:39:36,170 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:39:36,170 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:39:36,170 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:39:36,170 INFO L85 PathProgramCache]: Analyzing trace with hash 867282317, now seen corresponding path program 7 times [2025-03-08 00:39:36,170 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:39:36,170 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [688785384] [2025-03-08 00:39:36,170 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-08 00:39:36,170 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:39:36,175 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 27 statements into 1 equivalence classes. [2025-03-08 00:39:36,236 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 27 of 27 statements. [2025-03-08 00:39:36,237 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 00:39:36,237 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 00:39:36,238 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [660343374] [2025-03-08 00:39:36,239 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-08 00:39:36,239 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:39:36,240 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 00:39:36,242 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 00:39:36,245 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 00:39:36,283 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 27 statements into 1 equivalence classes. [2025-03-08 00:39:36,317 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 27 of 27 statements. [2025-03-08 00:39:36,317 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 00:39:36,317 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:39:36,318 INFO L256 TraceCheckSpWp]: Trace formula consists of 144 conjuncts, 65 conjuncts are in the unsatisfiable core [2025-03-08 00:39:36,322 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 00:39:36,354 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-08 00:39:36,361 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-08 00:39:36,390 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 18 [2025-03-08 00:39:36,398 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 18 [2025-03-08 00:39:36,442 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:39:36,442 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 28 [2025-03-08 00:39:36,454 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:39:36,454 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 28 [2025-03-08 00:39:36,893 INFO L349 Elim1Store]: treesize reduction 197, result has 23.9 percent of original size [2025-03-08 00:39:36,893 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 7 select indices, 7 select index equivalence classes, 3 disjoint index pairs (out of 21 index pairs), introduced 7 new quantified variables, introduced 27 case distinctions, treesize of input 64 treesize of output 91 [2025-03-08 00:39:36,933 INFO L349 Elim1Store]: treesize reduction 12, result has 60.0 percent of original size [2025-03-08 00:39:36,933 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 144 treesize of output 133 [2025-03-08 00:39:36,977 INFO L349 Elim1Store]: treesize reduction 141, result has 0.7 percent of original size [2025-03-08 00:39:36,978 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 5 select indices, 5 select index equivalence classes, 7 disjoint index pairs (out of 10 index pairs), introduced 7 new quantified variables, introduced 6 case distinctions, treesize of input 101 treesize of output 165 [2025-03-08 00:39:37,006 WARN L214 Elim1Store]: Array PQE input equivalent to false [2025-03-08 00:39:37,761 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:39:37,762 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 300 treesize of output 268 [2025-03-08 00:39:37,769 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 172 treesize of output 148 [2025-03-08 00:39:37,771 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-08 00:39:37,771 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-08 00:39:37,772 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-08 00:39:37,772 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-08 00:39:37,773 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-08 00:39:37,774 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-08 00:39:37,775 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 39 treesize of output 23 [2025-03-08 00:39:37,802 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 4 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-08 00:39:37,803 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 00:39:39,954 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:39:39,955 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [688785384] [2025-03-08 00:39:39,955 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 00:39:39,955 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [660343374] [2025-03-08 00:39:39,955 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [660343374] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 00:39:39,955 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-08 00:39:39,955 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20] total 20 [2025-03-08 00:39:39,955 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [446346749] [2025-03-08 00:39:39,955 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-08 00:39:39,955 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2025-03-08 00:39:39,955 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:39:39,956 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2025-03-08 00:39:39,956 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=91, Invalid=611, Unknown=0, NotChecked=0, Total=702 [2025-03-08 00:39:39,956 INFO L87 Difference]: Start difference. First operand 48 states and 52 transitions. Second operand has 20 states, 20 states have (on average 1.15) internal successors, (23), 17 states have internal predecessors, (23), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-08 00:39:40,859 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:39:40,859 INFO L93 Difference]: Finished difference Result 69 states and 77 transitions. [2025-03-08 00:39:40,859 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2025-03-08 00:39:40,859 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 1.15) internal successors, (23), 17 states have internal predecessors, (23), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 27 [2025-03-08 00:39:40,859 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:39:40,860 INFO L225 Difference]: With dead ends: 69 [2025-03-08 00:39:40,860 INFO L226 Difference]: Without dead ends: 66 [2025-03-08 00:39:40,860 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 44 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 244 ImplicationChecksByTransitivity, 2.6s TimeCoverageRelationStatistics Valid=146, Invalid=1044, Unknown=0, NotChecked=0, Total=1190 [2025-03-08 00:39:40,861 INFO L435 NwaCegarLoop]: 19 mSDtfsCounter, 36 mSDsluCounter, 165 mSDsCounter, 0 mSdLazyCounter, 300 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 36 SdHoareTripleChecker+Valid, 184 SdHoareTripleChecker+Invalid, 306 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 300 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-03-08 00:39:40,861 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [36 Valid, 184 Invalid, 306 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 300 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-03-08 00:39:40,861 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 66 states. [2025-03-08 00:39:40,871 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 66 to 59. [2025-03-08 00:39:40,871 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 48 states have (on average 1.1458333333333333) internal successors, (55), 48 states have internal predecessors, (55), 5 states have call successors, (5), 5 states have call predecessors, (5), 5 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2025-03-08 00:39:40,872 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 65 transitions. [2025-03-08 00:39:40,872 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 65 transitions. Word has length 27 [2025-03-08 00:39:40,872 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:39:40,872 INFO L471 AbstractCegarLoop]: Abstraction has 59 states and 65 transitions. [2025-03-08 00:39:40,872 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 1.15) internal successors, (23), 17 states have internal predecessors, (23), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-08 00:39:40,872 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 65 transitions. [2025-03-08 00:39:40,873 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2025-03-08 00:39:40,873 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:39:40,873 INFO L218 NwaCegarLoop]: trace histogram [4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 00:39:40,879 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2025-03-08 00:39:41,073 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:39:41,073 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:39:41,074 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:39:41,074 INFO L85 PathProgramCache]: Analyzing trace with hash 1460085076, now seen corresponding path program 8 times [2025-03-08 00:39:41,074 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:39:41,074 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1569711889] [2025-03-08 00:39:41,074 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 00:39:41,074 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:39:41,079 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 28 statements into 2 equivalence classes. [2025-03-08 00:39:41,085 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 28 of 28 statements. [2025-03-08 00:39:41,085 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 00:39:41,085 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:39:41,187 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 3 proven. 13 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-08 00:39:41,187 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:39:41,187 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1569711889] [2025-03-08 00:39:41,188 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1569711889] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 00:39:41,188 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1359535125] [2025-03-08 00:39:41,188 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 00:39:41,188 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:39:41,188 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 00:39:41,190 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 00:39:41,191 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 00:39:41,232 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 28 statements into 2 equivalence classes. [2025-03-08 00:39:41,250 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 28 of 28 statements. [2025-03-08 00:39:41,250 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 00:39:41,250 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:39:41,251 INFO L256 TraceCheckSpWp]: Trace formula consists of 155 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-03-08 00:39:41,252 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 00:39:41,314 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 10 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-08 00:39:41,314 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 00:39:41,378 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 10 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-08 00:39:41,378 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1359535125] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 00:39:41,378 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 00:39:41,378 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 11] total 17 [2025-03-08 00:39:41,378 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [439632312] [2025-03-08 00:39:41,378 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 00:39:41,378 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2025-03-08 00:39:41,378 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:39:41,379 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2025-03-08 00:39:41,379 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=75, Invalid=197, Unknown=0, NotChecked=0, Total=272 [2025-03-08 00:39:41,379 INFO L87 Difference]: Start difference. First operand 59 states and 65 transitions. Second operand has 17 states, 17 states have (on average 1.9411764705882353) internal successors, (33), 17 states have internal predecessors, (33), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-08 00:39:41,499 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:39:41,499 INFO L93 Difference]: Finished difference Result 82 states and 89 transitions. [2025-03-08 00:39:41,499 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2025-03-08 00:39:41,500 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 1.9411764705882353) internal successors, (33), 17 states have internal predecessors, (33), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 28 [2025-03-08 00:39:41,500 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:39:41,500 INFO L225 Difference]: With dead ends: 82 [2025-03-08 00:39:41,500 INFO L226 Difference]: Without dead ends: 79 [2025-03-08 00:39:41,501 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 42 SyntacticMatches, 8 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 161 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=113, Invalid=307, Unknown=0, NotChecked=0, Total=420 [2025-03-08 00:39:41,501 INFO L435 NwaCegarLoop]: 25 mSDtfsCounter, 4 mSDsluCounter, 135 mSDsCounter, 0 mSdLazyCounter, 180 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 160 SdHoareTripleChecker+Invalid, 186 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 180 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 00:39:41,501 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 160 Invalid, 186 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 180 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 00:39:41,501 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 79 states. [2025-03-08 00:39:41,513 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 79 to 67. [2025-03-08 00:39:41,513 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 67 states, 54 states have (on average 1.1481481481481481) internal successors, (62), 54 states have internal predecessors, (62), 6 states have call successors, (6), 6 states have call predecessors, (6), 6 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-03-08 00:39:41,513 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 74 transitions. [2025-03-08 00:39:41,513 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 74 transitions. Word has length 28 [2025-03-08 00:39:41,514 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:39:41,514 INFO L471 AbstractCegarLoop]: Abstraction has 67 states and 74 transitions. [2025-03-08 00:39:41,514 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 1.9411764705882353) internal successors, (33), 17 states have internal predecessors, (33), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-08 00:39:41,514 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 74 transitions. [2025-03-08 00:39:41,514 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2025-03-08 00:39:41,514 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:39:41,514 INFO L218 NwaCegarLoop]: trace histogram [4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 00:39:41,521 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 00:39:41,714 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,SelfDestructingSolverStorable10 [2025-03-08 00:39:41,715 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:39:41,715 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:39:41,715 INFO L85 PathProgramCache]: Analyzing trace with hash 1115979804, now seen corresponding path program 9 times [2025-03-08 00:39:41,715 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:39:41,715 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [222641806] [2025-03-08 00:39:41,715 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-08 00:39:41,715 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:39:41,720 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 28 statements into 4 equivalence classes. [2025-03-08 00:39:41,743 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) and asserted 28 of 28 statements. [2025-03-08 00:39:41,744 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2025-03-08 00:39:41,744 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:39:41,833 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 7 proven. 9 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-08 00:39:41,834 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:39:41,834 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [222641806] [2025-03-08 00:39:41,834 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [222641806] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 00:39:41,834 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1838307690] [2025-03-08 00:39:41,834 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-08 00:39:41,834 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:39:41,834 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 00:39:41,836 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 00:39:41,837 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 00:39:41,872 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 28 statements into 4 equivalence classes. [2025-03-08 00:39:41,909 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) and asserted 28 of 28 statements. [2025-03-08 00:39:41,910 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2025-03-08 00:39:41,910 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:39:41,910 INFO L256 TraceCheckSpWp]: Trace formula consists of 149 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-03-08 00:39:41,911 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 00:39:41,969 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 14 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-08 00:39:41,970 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 00:39:42,010 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 10 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-08 00:39:42,010 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1838307690] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 00:39:42,010 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 00:39:42,010 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 11] total 17 [2025-03-08 00:39:42,010 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [622216567] [2025-03-08 00:39:42,010 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 00:39:42,011 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2025-03-08 00:39:42,011 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:39:42,011 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2025-03-08 00:39:42,011 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=75, Invalid=197, Unknown=0, NotChecked=0, Total=272 [2025-03-08 00:39:42,011 INFO L87 Difference]: Start difference. First operand 67 states and 74 transitions. Second operand has 17 states, 17 states have (on average 1.9411764705882353) internal successors, (33), 17 states have internal predecessors, (33), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-08 00:39:42,090 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:39:42,090 INFO L93 Difference]: Finished difference Result 83 states and 90 transitions. [2025-03-08 00:39:42,090 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-03-08 00:39:42,090 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 1.9411764705882353) internal successors, (33), 17 states have internal predecessors, (33), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 28 [2025-03-08 00:39:42,091 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:39:42,093 INFO L225 Difference]: With dead ends: 83 [2025-03-08 00:39:42,093 INFO L226 Difference]: Without dead ends: 74 [2025-03-08 00:39:42,093 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 68 GetRequests, 43 SyntacticMatches, 7 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 156 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=108, Invalid=272, Unknown=0, NotChecked=0, Total=380 [2025-03-08 00:39:42,094 INFO L435 NwaCegarLoop]: 21 mSDtfsCounter, 5 mSDsluCounter, 103 mSDsCounter, 0 mSdLazyCounter, 99 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 107 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 99 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 00:39:42,094 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 124 Invalid, 107 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 99 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 00:39:42,094 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2025-03-08 00:39:42,110 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 68. [2025-03-08 00:39:42,111 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 68 states, 55 states have (on average 1.1272727272727272) internal successors, (62), 55 states have internal predecessors, (62), 6 states have call successors, (6), 6 states have call predecessors, (6), 6 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-03-08 00:39:42,111 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 68 states to 68 states and 74 transitions. [2025-03-08 00:39:42,112 INFO L78 Accepts]: Start accepts. Automaton has 68 states and 74 transitions. Word has length 28 [2025-03-08 00:39:42,112 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:39:42,112 INFO L471 AbstractCegarLoop]: Abstraction has 68 states and 74 transitions. [2025-03-08 00:39:42,112 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 1.9411764705882353) internal successors, (33), 17 states have internal predecessors, (33), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-08 00:39:42,112 INFO L276 IsEmpty]: Start isEmpty. Operand 68 states and 74 transitions. [2025-03-08 00:39:42,112 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2025-03-08 00:39:42,113 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:39:42,113 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 00:39:42,121 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 00:39:42,313 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:39:42,313 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:39:42,313 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:39:42,314 INFO L85 PathProgramCache]: Analyzing trace with hash -1981971147, now seen corresponding path program 10 times [2025-03-08 00:39:42,314 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:39:42,314 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1710243500] [2025-03-08 00:39:42,314 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-08 00:39:42,314 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:39:42,319 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 29 statements into 2 equivalence classes. [2025-03-08 00:39:42,352 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 29 of 29 statements. [2025-03-08 00:39:42,352 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-08 00:39:42,352 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 00:39:42,354 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [151406047] [2025-03-08 00:39:42,354 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-08 00:39:42,354 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:39:42,354 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 00:39:42,357 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 00:39:42,357 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 00:39:42,395 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 29 statements into 2 equivalence classes. [2025-03-08 00:39:42,453 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 29 of 29 statements. [2025-03-08 00:39:42,453 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-08 00:39:42,453 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:39:42,455 INFO L256 TraceCheckSpWp]: Trace formula consists of 160 conjuncts, 67 conjuncts are in the unsatisfiable core [2025-03-08 00:39:42,457 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 00:39:42,476 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-08 00:39:42,478 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-08 00:39:42,494 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 18 [2025-03-08 00:39:42,499 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 18 [2025-03-08 00:39:42,535 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:39:42,536 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 28 [2025-03-08 00:39:42,545 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:39:42,545 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 28 [2025-03-08 00:39:42,577 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:39:42,578 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 33 treesize of output 38 [2025-03-08 00:39:42,591 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:39:42,591 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 33 treesize of output 38 [2025-03-08 00:39:42,982 INFO L349 Elim1Store]: treesize reduction 12, result has 60.0 percent of original size [2025-03-08 00:39:42,982 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 158 treesize of output 143 [2025-03-08 00:39:43,132 INFO L349 Elim1Store]: treesize reduction 261, result has 24.3 percent of original size [2025-03-08 00:39:43,133 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 9 select indices, 9 select index equivalence classes, 6 disjoint index pairs (out of 36 index pairs), introduced 9 new quantified variables, introduced 44 case distinctions, treesize of input 78 treesize of output 119 [2025-03-08 00:39:43,177 INFO L349 Elim1Store]: treesize reduction 188, result has 0.5 percent of original size [2025-03-08 00:39:43,177 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 6 select indices, 6 select index equivalence classes, 11 disjoint index pairs (out of 15 index pairs), introduced 8 new quantified variables, introduced 8 case distinctions, treesize of input 106 treesize of output 173 [2025-03-08 00:39:44,478 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 429 treesize of output 373 [2025-03-08 00:39:44,516 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:39:44,516 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 6 select indices, 6 select index equivalence classes, 6 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 9 case distinctions, treesize of input 723 treesize of output 641 [2025-03-08 00:39:44,536 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:39:44,537 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 229 treesize of output 165 [2025-03-08 00:39:45,256 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 4 proven. 20 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-08 00:39:45,256 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 00:39:47,461 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:39:47,462 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1710243500] [2025-03-08 00:39:47,462 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 00:39:47,462 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [151406047] [2025-03-08 00:39:47,462 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [151406047] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 00:39:47,462 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-08 00:39:47,462 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19] total 19 [2025-03-08 00:39:47,462 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [208252652] [2025-03-08 00:39:47,462 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-08 00:39:47,462 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2025-03-08 00:39:47,462 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:39:47,462 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2025-03-08 00:39:47,462 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=79, Invalid=571, Unknown=0, NotChecked=0, Total=650 [2025-03-08 00:39:47,463 INFO L87 Difference]: Start difference. First operand 68 states and 74 transitions. Second operand has 19 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 17 states have internal predecessors, (25), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-08 00:39:47,850 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:39:47,851 INFO L93 Difference]: Finished difference Result 91 states and 101 transitions. [2025-03-08 00:39:47,851 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2025-03-08 00:39:47,851 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 17 states have internal predecessors, (25), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 29 [2025-03-08 00:39:47,851 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:39:47,852 INFO L225 Difference]: With dead ends: 91 [2025-03-08 00:39:47,852 INFO L226 Difference]: Without dead ends: 88 [2025-03-08 00:39:47,852 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 14 SyntacticMatches, 1 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 119 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=79, Invalid=571, Unknown=0, NotChecked=0, Total=650 [2025-03-08 00:39:47,852 INFO L435 NwaCegarLoop]: 22 mSDtfsCounter, 15 mSDsluCounter, 188 mSDsCounter, 0 mSdLazyCounter, 315 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 210 SdHoareTripleChecker+Invalid, 317 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 315 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2025-03-08 00:39:47,852 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 210 Invalid, 317 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 315 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2025-03-08 00:39:47,853 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 88 states. [2025-03-08 00:39:47,879 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 88 to 79. [2025-03-08 00:39:47,879 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 79 states, 64 states have (on average 1.140625) internal successors, (73), 64 states have internal predecessors, (73), 7 states have call successors, (7), 7 states have call predecessors, (7), 7 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2025-03-08 00:39:47,880 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 87 transitions. [2025-03-08 00:39:47,880 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 87 transitions. Word has length 29 [2025-03-08 00:39:47,880 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:39:47,880 INFO L471 AbstractCegarLoop]: Abstraction has 79 states and 87 transitions. [2025-03-08 00:39:47,880 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 17 states have internal predecessors, (25), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-08 00:39:47,880 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 87 transitions. [2025-03-08 00:39:47,880 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2025-03-08 00:39:47,880 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:39:47,881 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 00:39:47,887 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 00:39:48,081 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,SelfDestructingSolverStorable12 [2025-03-08 00:39:48,081 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:39:48,081 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:39:48,081 INFO L85 PathProgramCache]: Analyzing trace with hash 765797180, now seen corresponding path program 11 times [2025-03-08 00:39:48,082 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:39:48,082 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [648326859] [2025-03-08 00:39:48,082 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-08 00:39:48,082 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:39:48,088 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 30 statements into 5 equivalence classes. [2025-03-08 00:39:48,098 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 5 check-sat command(s) and asserted 30 of 30 statements. [2025-03-08 00:39:48,098 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 5 check-sat command(s) [2025-03-08 00:39:48,098 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:39:48,232 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 10 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-08 00:39:48,233 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:39:48,233 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [648326859] [2025-03-08 00:39:48,233 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [648326859] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 00:39:48,233 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1104085045] [2025-03-08 00:39:48,233 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-08 00:39:48,233 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:39:48,234 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 00:39:48,235 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 00:39:48,237 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 00:39:48,276 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 30 statements into 5 equivalence classes. [2025-03-08 00:39:48,313 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 5 check-sat command(s) and asserted 30 of 30 statements. [2025-03-08 00:39:48,314 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 5 check-sat command(s) [2025-03-08 00:39:48,314 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:39:48,315 INFO L256 TraceCheckSpWp]: Trace formula consists of 171 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-03-08 00:39:48,315 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 00:39:48,375 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 14 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-08 00:39:48,375 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 00:39:48,443 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 10 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-08 00:39:48,443 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1104085045] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 00:39:48,443 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 00:39:48,443 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13, 13] total 18 [2025-03-08 00:39:48,443 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1305387998] [2025-03-08 00:39:48,443 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 00:39:48,443 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2025-03-08 00:39:48,443 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:39:48,444 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2025-03-08 00:39:48,444 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=83, Invalid=223, Unknown=0, NotChecked=0, Total=306 [2025-03-08 00:39:48,444 INFO L87 Difference]: Start difference. First operand 79 states and 87 transitions. Second operand has 18 states, 18 states have (on average 1.7777777777777777) internal successors, (32), 18 states have internal predecessors, (32), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-08 00:39:48,612 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:39:48,612 INFO L93 Difference]: Finished difference Result 107 states and 116 transitions. [2025-03-08 00:39:48,612 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2025-03-08 00:39:48,612 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 1.7777777777777777) internal successors, (32), 18 states have internal predecessors, (32), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 30 [2025-03-08 00:39:48,612 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:39:48,613 INFO L225 Difference]: With dead ends: 107 [2025-03-08 00:39:48,613 INFO L226 Difference]: Without dead ends: 104 [2025-03-08 00:39:48,613 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 77 GetRequests, 44 SyntacticMatches, 11 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 208 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=152, Invalid=400, Unknown=0, NotChecked=0, Total=552 [2025-03-08 00:39:48,614 INFO L435 NwaCegarLoop]: 25 mSDtfsCounter, 4 mSDsluCounter, 167 mSDsCounter, 0 mSdLazyCounter, 260 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 192 SdHoareTripleChecker+Invalid, 266 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 260 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 00:39:48,614 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 192 Invalid, 266 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 260 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 00:39:48,614 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 104 states. [2025-03-08 00:39:48,631 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 104 to 87. [2025-03-08 00:39:48,632 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 87 states, 70 states have (on average 1.1428571428571428) internal successors, (80), 70 states have internal predecessors, (80), 8 states have call successors, (8), 8 states have call predecessors, (8), 8 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2025-03-08 00:39:48,632 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 87 states to 87 states and 96 transitions. [2025-03-08 00:39:48,632 INFO L78 Accepts]: Start accepts. Automaton has 87 states and 96 transitions. Word has length 30 [2025-03-08 00:39:48,632 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:39:48,633 INFO L471 AbstractCegarLoop]: Abstraction has 87 states and 96 transitions. [2025-03-08 00:39:48,633 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 1.7777777777777777) internal successors, (32), 18 states have internal predecessors, (32), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-08 00:39:48,633 INFO L276 IsEmpty]: Start isEmpty. Operand 87 states and 96 transitions. [2025-03-08 00:39:48,633 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2025-03-08 00:39:48,633 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:39:48,633 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 00:39:48,640 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2025-03-08 00:39:48,834 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,SelfDestructingSolverStorable13 [2025-03-08 00:39:48,834 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:39:48,834 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:39:48,834 INFO L85 PathProgramCache]: Analyzing trace with hash -1311531660, now seen corresponding path program 12 times [2025-03-08 00:39:48,834 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:39:48,834 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [743807421] [2025-03-08 00:39:48,834 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-08 00:39:48,834 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:39:48,839 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 30 statements into 4 equivalence classes. [2025-03-08 00:39:48,853 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) and asserted 30 of 30 statements. [2025-03-08 00:39:48,853 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2025-03-08 00:39:48,853 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:39:48,960 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 11 proven. 14 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-08 00:39:48,961 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:39:48,961 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [743807421] [2025-03-08 00:39:48,961 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [743807421] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 00:39:48,961 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1990711417] [2025-03-08 00:39:48,961 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-08 00:39:48,961 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:39:48,961 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 00:39:48,963 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 00:39:48,964 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 00:39:49,008 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 30 statements into 4 equivalence classes. [2025-03-08 00:39:49,042 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) and asserted 30 of 30 statements. [2025-03-08 00:39:49,042 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2025-03-08 00:39:49,042 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:39:49,043 INFO L256 TraceCheckSpWp]: Trace formula consists of 165 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-03-08 00:39:49,044 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 00:39:49,122 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 19 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-08 00:39:49,122 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 00:39:49,185 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 15 proven. 10 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-08 00:39:49,186 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1990711417] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 00:39:49,186 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 00:39:49,186 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13, 13] total 20 [2025-03-08 00:39:49,186 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [123527669] [2025-03-08 00:39:49,186 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 00:39:49,186 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2025-03-08 00:39:49,186 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:39:49,186 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2025-03-08 00:39:49,186 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=101, Invalid=279, Unknown=0, NotChecked=0, Total=380 [2025-03-08 00:39:49,187 INFO L87 Difference]: Start difference. First operand 87 states and 96 transitions. Second operand has 20 states, 20 states have (on average 1.8) internal successors, (36), 20 states have internal predecessors, (36), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-08 00:39:49,282 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:39:49,283 INFO L93 Difference]: Finished difference Result 108 states and 117 transitions. [2025-03-08 00:39:49,283 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2025-03-08 00:39:49,283 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 1.8) internal successors, (36), 20 states have internal predecessors, (36), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 30 [2025-03-08 00:39:49,283 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:39:49,283 INFO L225 Difference]: With dead ends: 108 [2025-03-08 00:39:49,284 INFO L226 Difference]: Without dead ends: 98 [2025-03-08 00:39:49,284 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 75 GetRequests, 44 SyntacticMatches, 9 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 237 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=151, Invalid=401, Unknown=0, NotChecked=0, Total=552 [2025-03-08 00:39:49,284 INFO L435 NwaCegarLoop]: 21 mSDtfsCounter, 6 mSDsluCounter, 71 mSDsCounter, 0 mSdLazyCounter, 96 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 92 SdHoareTripleChecker+Invalid, 111 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 96 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 00:39:49,284 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 92 Invalid, 111 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 96 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 00:39:49,284 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2025-03-08 00:39:49,304 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 88. [2025-03-08 00:39:49,305 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 88 states, 71 states have (on average 1.1267605633802817) internal successors, (80), 71 states have internal predecessors, (80), 8 states have call successors, (8), 8 states have call predecessors, (8), 8 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2025-03-08 00:39:49,305 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 96 transitions. [2025-03-08 00:39:49,305 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 96 transitions. Word has length 30 [2025-03-08 00:39:49,305 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:39:49,305 INFO L471 AbstractCegarLoop]: Abstraction has 88 states and 96 transitions. [2025-03-08 00:39:49,306 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 1.8) internal successors, (36), 20 states have internal predecessors, (36), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-08 00:39:49,306 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 96 transitions. [2025-03-08 00:39:49,306 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2025-03-08 00:39:49,306 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:39:49,306 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 00:39:49,316 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 00:39:49,510 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,SelfDestructingSolverStorable14 [2025-03-08 00:39:49,510 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:39:49,510 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:39:49,510 INFO L85 PathProgramCache]: Analyzing trace with hash -2030059443, now seen corresponding path program 13 times [2025-03-08 00:39:49,510 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:39:49,511 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1956318801] [2025-03-08 00:39:49,511 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-08 00:39:49,511 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:39:49,516 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-08 00:39:49,551 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-08 00:39:49,551 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 00:39:49,551 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 00:39:49,552 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1171550964] [2025-03-08 00:39:49,553 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-08 00:39:49,553 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:39:49,553 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 00:39:49,555 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 00:39:49,556 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 00:39:49,600 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-08 00:39:49,697 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-08 00:39:49,697 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 00:39:49,697 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:39:49,699 INFO L256 TraceCheckSpWp]: Trace formula consists of 176 conjuncts, 84 conjuncts are in the unsatisfiable core [2025-03-08 00:39:49,701 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 00:39:49,745 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-08 00:39:49,750 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-08 00:39:49,773 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 18 [2025-03-08 00:39:49,780 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 18 [2025-03-08 00:39:49,820 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:39:49,820 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 28 [2025-03-08 00:39:49,834 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:39:49,834 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 28 [2025-03-08 00:39:49,890 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:39:49,890 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 33 treesize of output 38 [2025-03-08 00:39:49,902 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:39:49,903 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 33 treesize of output 38 [2025-03-08 00:39:49,968 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:39:49,968 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 10 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 40 treesize of output 48 [2025-03-08 00:39:49,998 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:39:49,998 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 10 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 40 treesize of output 48 [2025-03-08 00:39:50,645 INFO L349 Elim1Store]: treesize reduction 325, result has 24.6 percent of original size [2025-03-08 00:39:50,646 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 11 select indices, 11 select index equivalence classes, 10 disjoint index pairs (out of 55 index pairs), introduced 11 new quantified variables, introduced 65 case distinctions, treesize of input 92 treesize of output 147 [2025-03-08 00:39:50,684 INFO L349 Elim1Store]: treesize reduction 12, result has 60.0 percent of original size [2025-03-08 00:39:50,684 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 172 treesize of output 153 [2025-03-08 00:39:50,733 INFO L349 Elim1Store]: treesize reduction 235, result has 0.4 percent of original size [2025-03-08 00:39:50,734 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 7 select indices, 7 select index equivalence classes, 16 disjoint index pairs (out of 21 index pairs), introduced 9 new quantified variables, introduced 10 case distinctions, treesize of input 111 treesize of output 181 [2025-03-08 00:39:50,833 INFO L349 Elim1Store]: treesize reduction 227, result has 25.8 percent of original size [2025-03-08 00:39:50,833 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 7 select indices, 7 select index equivalence classes, 16 disjoint index pairs (out of 21 index pairs), introduced 7 new quantified variables, introduced 10 case distinctions, treesize of input 139 treesize of output 130 [2025-03-08 00:39:52,450 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:39:52,451 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 5 select indices, 5 select index equivalence classes, 10 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 10 case distinctions, treesize of input 309 treesize of output 209 [2025-03-08 00:39:52,459 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:39:52,459 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 5 select indices, 5 select index equivalence classes, 10 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 10 case distinctions, treesize of input 184 treesize of output 124 [2025-03-08 00:39:52,494 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 4 proven. 30 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-08 00:39:52,494 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 00:39:55,958 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:39:55,958 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1956318801] [2025-03-08 00:39:55,958 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 00:39:55,958 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1171550964] [2025-03-08 00:39:55,958 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1171550964] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 00:39:55,958 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-08 00:39:55,958 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [26] total 26 [2025-03-08 00:39:55,958 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [69592052] [2025-03-08 00:39:55,958 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-08 00:39:55,959 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2025-03-08 00:39:55,959 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:39:55,959 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2025-03-08 00:39:55,959 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=135, Invalid=1055, Unknown=0, NotChecked=0, Total=1190 [2025-03-08 00:39:55,959 INFO L87 Difference]: Start difference. First operand 88 states and 96 transitions. Second operand has 26 states, 26 states have (on average 1.0384615384615385) internal successors, (27), 23 states have internal predecessors, (27), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-08 00:39:58,206 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:39:58,206 INFO L93 Difference]: Finished difference Result 113 states and 125 transitions. [2025-03-08 00:39:58,206 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2025-03-08 00:39:58,206 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 26 states have (on average 1.0384615384615385) internal successors, (27), 23 states have internal predecessors, (27), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 31 [2025-03-08 00:39:58,206 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:39:58,207 INFO L225 Difference]: With dead ends: 113 [2025-03-08 00:39:58,207 INFO L226 Difference]: Without dead ends: 110 [2025-03-08 00:39:58,207 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 52 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 474 ImplicationChecksByTransitivity, 5.4s TimeCoverageRelationStatistics Valid=214, Invalid=1766, Unknown=0, NotChecked=0, Total=1980 [2025-03-08 00:39:58,208 INFO L435 NwaCegarLoop]: 19 mSDtfsCounter, 65 mSDsluCounter, 210 mSDsCounter, 0 mSdLazyCounter, 530 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 65 SdHoareTripleChecker+Valid, 229 SdHoareTripleChecker+Invalid, 539 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 530 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2025-03-08 00:39:58,208 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [65 Valid, 229 Invalid, 539 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 530 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2025-03-08 00:39:58,208 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 110 states. [2025-03-08 00:39:58,233 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 110 to 99. [2025-03-08 00:39:58,234 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 99 states, 80 states have (on average 1.1375) internal successors, (91), 80 states have internal predecessors, (91), 9 states have call successors, (9), 9 states have call predecessors, (9), 9 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2025-03-08 00:39:58,235 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 109 transitions. [2025-03-08 00:39:58,235 INFO L78 Accepts]: Start accepts. Automaton has 99 states and 109 transitions. Word has length 31 [2025-03-08 00:39:58,236 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:39:58,236 INFO L471 AbstractCegarLoop]: Abstraction has 99 states and 109 transitions. [2025-03-08 00:39:58,236 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 26 states have (on average 1.0384615384615385) internal successors, (27), 23 states have internal predecessors, (27), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-08 00:39:58,236 INFO L276 IsEmpty]: Start isEmpty. Operand 99 states and 109 transitions. [2025-03-08 00:39:58,236 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2025-03-08 00:39:58,237 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:39:58,237 INFO L218 NwaCegarLoop]: trace histogram [6, 5, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 00:39:58,243 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2025-03-08 00:39:58,437 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,SelfDestructingSolverStorable15 [2025-03-08 00:39:58,437 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:39:58,438 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:39:58,438 INFO L85 PathProgramCache]: Analyzing trace with hash 1465383060, now seen corresponding path program 14 times [2025-03-08 00:39:58,438 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:39:58,438 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [730734319] [2025-03-08 00:39:58,438 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 00:39:58,438 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:39:58,443 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 32 statements into 2 equivalence classes. [2025-03-08 00:39:58,454 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 32 of 32 statements. [2025-03-08 00:39:58,454 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 00:39:58,454 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:39:58,596 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 10 proven. 26 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-08 00:39:58,596 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:39:58,596 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [730734319] [2025-03-08 00:39:58,596 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [730734319] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 00:39:58,596 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1627565651] [2025-03-08 00:39:58,596 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 00:39:58,597 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:39:58,597 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 00:39:58,599 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 00:39:58,608 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 00:39:58,654 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 32 statements into 2 equivalence classes. [2025-03-08 00:39:58,671 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 32 of 32 statements. [2025-03-08 00:39:58,671 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 00:39:58,671 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:39:58,672 INFO L256 TraceCheckSpWp]: Trace formula consists of 187 conjuncts, 14 conjuncts are in the unsatisfiable core [2025-03-08 00:39:58,673 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 00:39:58,752 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 19 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-08 00:39:58,752 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 00:39:58,836 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 15 proven. 21 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-08 00:39:58,836 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1627565651] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 00:39:58,836 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 00:39:58,836 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15, 15] total 23 [2025-03-08 00:39:58,836 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1791312369] [2025-03-08 00:39:58,836 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 00:39:58,836 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2025-03-08 00:39:58,836 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:39:58,837 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2025-03-08 00:39:58,837 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=131, Invalid=375, Unknown=0, NotChecked=0, Total=506 [2025-03-08 00:39:58,837 INFO L87 Difference]: Start difference. First operand 99 states and 109 transitions. Second operand has 23 states, 23 states have (on average 1.6956521739130435) internal successors, (39), 23 states have internal predecessors, (39), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-08 00:39:59,002 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:39:59,002 INFO L93 Difference]: Finished difference Result 133 states and 144 transitions. [2025-03-08 00:39:59,003 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2025-03-08 00:39:59,003 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 1.6956521739130435) internal successors, (39), 23 states have internal predecessors, (39), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 32 [2025-03-08 00:39:59,003 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:39:59,003 INFO L225 Difference]: With dead ends: 133 [2025-03-08 00:39:59,004 INFO L226 Difference]: Without dead ends: 130 [2025-03-08 00:39:59,004 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 83 GetRequests, 44 SyntacticMatches, 12 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 359 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=206, Invalid=606, Unknown=0, NotChecked=0, Total=812 [2025-03-08 00:39:59,004 INFO L435 NwaCegarLoop]: 25 mSDtfsCounter, 4 mSDsluCounter, 159 mSDsCounter, 0 mSdLazyCounter, 260 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 184 SdHoareTripleChecker+Invalid, 268 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 260 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 00:39:59,004 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 184 Invalid, 268 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 260 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 00:39:59,005 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2025-03-08 00:39:59,030 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 107. [2025-03-08 00:39:59,031 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 107 states, 86 states have (on average 1.1395348837209303) internal successors, (98), 86 states have internal predecessors, (98), 10 states have call successors, (10), 10 states have call predecessors, (10), 10 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2025-03-08 00:39:59,031 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 107 states to 107 states and 118 transitions. [2025-03-08 00:39:59,031 INFO L78 Accepts]: Start accepts. Automaton has 107 states and 118 transitions. Word has length 32 [2025-03-08 00:39:59,032 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:39:59,032 INFO L471 AbstractCegarLoop]: Abstraction has 107 states and 118 transitions. [2025-03-08 00:39:59,032 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 1.6956521739130435) internal successors, (39), 23 states have internal predecessors, (39), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-08 00:39:59,032 INFO L276 IsEmpty]: Start isEmpty. Operand 107 states and 118 transitions. [2025-03-08 00:39:59,032 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2025-03-08 00:39:59,032 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:39:59,032 INFO L218 NwaCegarLoop]: trace histogram [6, 5, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 00:39:59,038 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 00:39:59,234 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable16,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:39:59,234 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:39:59,234 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:39:59,234 INFO L85 PathProgramCache]: Analyzing trace with hash 1492698460, now seen corresponding path program 15 times [2025-03-08 00:39:59,234 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:39:59,234 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1178830984] [2025-03-08 00:39:59,234 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-08 00:39:59,234 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:39:59,239 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 32 statements into 5 equivalence classes. [2025-03-08 00:39:59,271 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 32 of 32 statements. [2025-03-08 00:39:59,271 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-03-08 00:39:59,271 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:39:59,398 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 16 proven. 20 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-08 00:39:59,399 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:39:59,399 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1178830984] [2025-03-08 00:39:59,399 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1178830984] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 00:39:59,399 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [916620699] [2025-03-08 00:39:59,399 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-08 00:39:59,399 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:39:59,399 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 00:39:59,401 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 00:39:59,402 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 00:39:59,450 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 32 statements into 5 equivalence classes. [2025-03-08 00:39:59,580 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 32 of 32 statements. [2025-03-08 00:39:59,580 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-03-08 00:39:59,581 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:39:59,582 INFO L256 TraceCheckSpWp]: Trace formula consists of 181 conjuncts, 14 conjuncts are in the unsatisfiable core [2025-03-08 00:39:59,582 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 00:39:59,658 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 25 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-08 00:39:59,658 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 00:39:59,721 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 21 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-08 00:39:59,722 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [916620699] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 00:39:59,722 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 00:39:59,722 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15, 15] total 23 [2025-03-08 00:39:59,722 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1184547734] [2025-03-08 00:39:59,722 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 00:39:59,722 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2025-03-08 00:39:59,722 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:39:59,722 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2025-03-08 00:39:59,723 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=131, Invalid=375, Unknown=0, NotChecked=0, Total=506 [2025-03-08 00:39:59,723 INFO L87 Difference]: Start difference. First operand 107 states and 118 transitions. Second operand has 23 states, 23 states have (on average 1.6956521739130435) internal successors, (39), 23 states have internal predecessors, (39), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-08 00:39:59,850 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:39:59,850 INFO L93 Difference]: Finished difference Result 134 states and 145 transitions. [2025-03-08 00:39:59,850 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2025-03-08 00:39:59,850 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 1.6956521739130435) internal successors, (39), 23 states have internal predecessors, (39), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 32 [2025-03-08 00:39:59,850 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:39:59,851 INFO L225 Difference]: With dead ends: 134 [2025-03-08 00:39:59,851 INFO L226 Difference]: Without dead ends: 123 [2025-03-08 00:39:59,851 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 82 GetRequests, 45 SyntacticMatches, 11 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 333 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=201, Invalid=555, Unknown=0, NotChecked=0, Total=756 [2025-03-08 00:39:59,851 INFO L435 NwaCegarLoop]: 21 mSDtfsCounter, 7 mSDsluCounter, 93 mSDsCounter, 0 mSdLazyCounter, 126 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 114 SdHoareTripleChecker+Invalid, 148 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 126 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 00:39:59,852 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 114 Invalid, 148 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 126 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 00:39:59,852 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 123 states. [2025-03-08 00:39:59,880 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 123 to 108. [2025-03-08 00:39:59,880 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 108 states, 87 states have (on average 1.1264367816091954) internal successors, (98), 87 states have internal predecessors, (98), 10 states have call successors, (10), 10 states have call predecessors, (10), 10 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2025-03-08 00:39:59,880 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 108 states to 108 states and 118 transitions. [2025-03-08 00:39:59,881 INFO L78 Accepts]: Start accepts. Automaton has 108 states and 118 transitions. Word has length 32 [2025-03-08 00:39:59,881 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:39:59,881 INFO L471 AbstractCegarLoop]: Abstraction has 108 states and 118 transitions. [2025-03-08 00:39:59,881 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 1.6956521739130435) internal successors, (39), 23 states have internal predecessors, (39), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-08 00:39:59,881 INFO L276 IsEmpty]: Start isEmpty. Operand 108 states and 118 transitions. [2025-03-08 00:39:59,881 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2025-03-08 00:39:59,881 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:39:59,881 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 00:39:59,887 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2025-03-08 00:40:00,081 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2025-03-08 00:40:00,082 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:40:00,082 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:40:00,082 INFO L85 PathProgramCache]: Analyzing trace with hash 59157302, now seen corresponding path program 1 times [2025-03-08 00:40:00,082 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:40:00,082 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1531752318] [2025-03-08 00:40:00,082 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 00:40:00,082 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:40:00,088 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 33 statements into 1 equivalence classes. [2025-03-08 00:40:00,114 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 33 of 33 statements. [2025-03-08 00:40:00,114 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 00:40:00,114 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 00:40:00,115 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2054256898] [2025-03-08 00:40:00,115 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 00:40:00,115 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:40:00,116 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 00:40:00,117 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-08 00:40:00,119 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2025-03-08 00:40:00,168 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 33 statements into 1 equivalence classes. [2025-03-08 00:40:00,223 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 33 of 33 statements. [2025-03-08 00:40:00,223 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 00:40:00,223 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:40:00,225 INFO L256 TraceCheckSpWp]: Trace formula consists of 150 conjuncts, 68 conjuncts are in the unsatisfiable core [2025-03-08 00:40:00,227 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 00:40:00,278 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-08 00:40:00,282 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-08 00:40:00,317 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 18 [2025-03-08 00:40:00,326 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 18 [2025-03-08 00:40:00,600 INFO L349 Elim1Store]: treesize reduction 12, result has 60.0 percent of original size [2025-03-08 00:40:00,601 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 130 treesize of output 123 [2025-03-08 00:40:00,646 INFO L349 Elim1Store]: treesize reduction 133, result has 23.1 percent of original size [2025-03-08 00:40:00,646 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 5 select indices, 5 select index equivalence classes, 1 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 14 case distinctions, treesize of input 50 treesize of output 63 [2025-03-08 00:40:00,683 INFO L349 Elim1Store]: treesize reduction 94, result has 1.1 percent of original size [2025-03-08 00:40:00,683 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 4 select indices, 4 select index equivalence classes, 4 disjoint index pairs (out of 6 index pairs), introduced 6 new quantified variables, introduced 4 case distinctions, treesize of input 96 treesize of output 157 [2025-03-08 00:40:00,727 INFO L349 Elim1Store]: treesize reduction 95, result has 22.8 percent of original size [2025-03-08 00:40:00,727 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 4 select indices, 4 select index equivalence classes, 4 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 4 case distinctions, treesize of input 124 treesize of output 70 [2025-03-08 00:40:01,239 INFO L349 Elim1Store]: treesize reduction 32, result has 52.2 percent of original size [2025-03-08 00:40:01,240 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 5 case distinctions, treesize of input 260 treesize of output 260 [2025-03-08 00:40:01,420 INFO L349 Elim1Store]: treesize reduction 208, result has 29.5 percent of original size [2025-03-08 00:40:01,421 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 7 select indices, 7 select index equivalence classes, 1 disjoint index pairs (out of 21 index pairs), introduced 7 new quantified variables, introduced 27 case distinctions, treesize of input 111 treesize of output 159 [2025-03-08 00:40:03,425 INFO L349 Elim1Store]: treesize reduction 94, result has 1.1 percent of original size [2025-03-08 00:40:03,426 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 4 select indices, 4 select index equivalence classes, 4 disjoint index pairs (out of 6 index pairs), introduced 6 new quantified variables, introduced 4 case distinctions, treesize of input 808 treesize of output 847 [2025-03-08 00:40:03,504 WARN L214 Elim1Store]: Array PQE input equivalent to false [2025-03-08 00:40:05,478 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:40:05,478 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 204 treesize of output 184 [2025-03-08 00:40:05,481 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:40:05,481 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 35 treesize of output 23 [2025-03-08 00:40:05,484 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 116 treesize of output 100 [2025-03-08 00:40:05,486 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-08 00:40:05,487 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-08 00:40:05,488 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-08 00:40:05,489 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-08 00:40:05,490 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-08 00:40:05,490 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 31 treesize of output 19 [2025-03-08 00:40:05,512 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 8 proven. 14 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-08 00:40:05,512 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 00:40:07,126 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:40:07,126 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1531752318] [2025-03-08 00:40:07,126 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 00:40:07,126 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2054256898] [2025-03-08 00:40:07,126 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2054256898] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 00:40:07,126 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-08 00:40:07,126 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [25] total 25 [2025-03-08 00:40:07,126 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1380235405] [2025-03-08 00:40:07,126 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-08 00:40:07,127 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2025-03-08 00:40:07,127 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:40:07,127 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2025-03-08 00:40:07,127 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=155, Invalid=775, Unknown=0, NotChecked=0, Total=930 [2025-03-08 00:40:07,128 INFO L87 Difference]: Start difference. First operand 108 states and 118 transitions. Second operand has 25 states, 25 states have (on average 1.08) internal successors, (27), 20 states have internal predecessors, (27), 3 states have call successors, (3), 3 states have call predecessors, (3), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-03-08 00:40:08,256 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:40:08,256 INFO L93 Difference]: Finished difference Result 129 states and 140 transitions. [2025-03-08 00:40:08,256 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2025-03-08 00:40:08,257 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 25 states have (on average 1.08) internal successors, (27), 20 states have internal predecessors, (27), 3 states have call successors, (3), 3 states have call predecessors, (3), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 33 [2025-03-08 00:40:08,257 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:40:08,257 INFO L225 Difference]: With dead ends: 129 [2025-03-08 00:40:08,257 INFO L226 Difference]: Without dead ends: 122 [2025-03-08 00:40:08,258 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 12 SyntacticMatches, 1 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 442 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=219, Invalid=1187, Unknown=0, NotChecked=0, Total=1406 [2025-03-08 00:40:08,258 INFO L435 NwaCegarLoop]: 16 mSDtfsCounter, 49 mSDsluCounter, 102 mSDsCounter, 0 mSdLazyCounter, 188 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 49 SdHoareTripleChecker+Valid, 118 SdHoareTripleChecker+Invalid, 201 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 188 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-08 00:40:08,258 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [49 Valid, 118 Invalid, 201 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 188 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-08 00:40:08,258 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 122 states. [2025-03-08 00:40:08,288 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 122 to 116. [2025-03-08 00:40:08,288 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 116 states, 93 states have (on average 1.118279569892473) internal successors, (104), 93 states have internal predecessors, (104), 11 states have call successors, (11), 11 states have call predecessors, (11), 11 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2025-03-08 00:40:08,289 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 116 states to 116 states and 126 transitions. [2025-03-08 00:40:08,289 INFO L78 Accepts]: Start accepts. Automaton has 116 states and 126 transitions. Word has length 33 [2025-03-08 00:40:08,289 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:40:08,289 INFO L471 AbstractCegarLoop]: Abstraction has 116 states and 126 transitions. [2025-03-08 00:40:08,289 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 25 states have (on average 1.08) internal successors, (27), 20 states have internal predecessors, (27), 3 states have call successors, (3), 3 states have call predecessors, (3), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-03-08 00:40:08,289 INFO L276 IsEmpty]: Start isEmpty. Operand 116 states and 126 transitions. [2025-03-08 00:40:08,289 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2025-03-08 00:40:08,289 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:40:08,289 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 00:40:08,295 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2025-03-08 00:40:08,491 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:40:08,491 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:40:08,491 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:40:08,491 INFO L85 PathProgramCache]: Analyzing trace with hash -1817733643, now seen corresponding path program 16 times [2025-03-08 00:40:08,491 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:40:08,491 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1444598991] [2025-03-08 00:40:08,492 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-08 00:40:08,492 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:40:08,497 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 33 statements into 2 equivalence classes. [2025-03-08 00:40:08,516 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 33 of 33 statements. [2025-03-08 00:40:08,516 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-08 00:40:08,516 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 00:40:08,517 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1323411071] [2025-03-08 00:40:08,517 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-08 00:40:08,517 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:40:08,517 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 00:40:08,519 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-08 00:40:08,520 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2025-03-08 00:40:08,577 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 33 statements into 2 equivalence classes. [2025-03-08 00:40:08,737 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 33 of 33 statements. [2025-03-08 00:40:08,737 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-08 00:40:08,737 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:40:08,739 INFO L256 TraceCheckSpWp]: Trace formula consists of 192 conjuncts, 91 conjuncts are in the unsatisfiable core [2025-03-08 00:40:08,742 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 00:40:08,770 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-08 00:40:08,777 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-08 00:40:08,814 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 18 [2025-03-08 00:40:08,821 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 18 [2025-03-08 00:40:08,855 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:40:08,855 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 28 [2025-03-08 00:40:08,865 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:40:08,865 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 28 [2025-03-08 00:40:08,900 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:40:08,900 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 33 treesize of output 38 [2025-03-08 00:40:08,912 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:40:08,912 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 33 treesize of output 38 [2025-03-08 00:40:08,952 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:40:08,952 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 10 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 40 treesize of output 48 [2025-03-08 00:40:08,970 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:40:08,970 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 10 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 40 treesize of output 48 [2025-03-08 00:40:09,027 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:40:09,027 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 5 select indices, 5 select index equivalence classes, 15 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 10 case distinctions, treesize of input 47 treesize of output 58 [2025-03-08 00:40:09,049 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:40:09,050 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 5 select indices, 5 select index equivalence classes, 15 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 10 case distinctions, treesize of input 47 treesize of output 58 [2025-03-08 00:40:09,701 INFO L349 Elim1Store]: treesize reduction 12, result has 60.0 percent of original size [2025-03-08 00:40:09,702 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 243 treesize of output 216 [2025-03-08 00:40:09,956 INFO L349 Elim1Store]: treesize reduction 389, result has 24.8 percent of original size [2025-03-08 00:40:09,957 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 13 select indices, 13 select index equivalence classes, 15 disjoint index pairs (out of 78 index pairs), introduced 13 new quantified variables, introduced 90 case distinctions, treesize of input 106 treesize of output 175 [2025-03-08 00:40:10,026 INFO L349 Elim1Store]: treesize reduction 282, result has 0.4 percent of original size [2025-03-08 00:40:10,026 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 8 select indices, 8 select index equivalence classes, 22 disjoint index pairs (out of 28 index pairs), introduced 10 new quantified variables, introduced 12 case distinctions, treesize of input 116 treesize of output 189 [2025-03-08 00:40:13,882 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:40:13,882 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 6 select indices, 6 select index equivalence classes, 15 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 15 case distinctions, treesize of input 771 treesize of output 667 [2025-03-08 00:40:13,899 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 340 treesize of output 292 [2025-03-08 00:40:13,902 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-08 00:40:13,902 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-08 00:40:13,903 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-08 00:40:13,903 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-08 00:40:13,904 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-08 00:40:13,905 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-08 00:40:13,905 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-08 00:40:13,906 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-08 00:40:13,907 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-08 00:40:13,907 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-08 00:40:13,908 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-08 00:40:13,909 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-08 00:40:13,910 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-08 00:40:13,910 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-08 00:40:13,911 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-08 00:40:13,911 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-08 00:40:13,912 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-08 00:40:13,912 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 7 select indices, 7 select index equivalence classes, 15 disjoint index pairs (out of 21 index pairs), introduced 6 new quantified variables, introduced 0 case distinctions, treesize of input 63 treesize of output 35 [2025-03-08 00:40:13,950 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 4 proven. 42 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-08 00:40:13,950 INFO L312 TraceCheckSpWp]: Computing backward predicates...