./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/array-patterns/array8_pattern.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 8fc3dc66 Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/array-patterns/array8_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 06625eaf591a62e295090a882d83c1e11aaafca7ac8895e7d4adcf51d5b26e02 --- Real Ultimate output --- This is Ultimate 0.3.0-?-8fc3dc6-m [2025-03-16 13:50:25,864 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-16 13:50:25,914 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-16 13:50:25,917 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-16 13:50:25,917 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-16 13:50:25,930 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-16 13:50:25,930 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-16 13:50:25,930 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-16 13:50:25,931 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-16 13:50:25,931 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-16 13:50:25,931 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-16 13:50:25,931 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-16 13:50:25,931 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-16 13:50:25,931 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-16 13:50:25,931 INFO L153 SettingsManager]: * Use SBE=true [2025-03-16 13:50:25,931 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-16 13:50:25,931 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-16 13:50:25,931 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-16 13:50:25,931 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-16 13:50:25,931 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-16 13:50:25,931 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-16 13:50:25,931 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-16 13:50:25,931 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-16 13:50:25,931 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-16 13:50:25,932 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-16 13:50:25,932 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-16 13:50:25,932 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-16 13:50:25,932 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-16 13:50:25,932 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-16 13:50:25,932 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-16 13:50:25,932 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-16 13:50:25,932 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-16 13:50:25,932 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-16 13:50:25,932 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-16 13:50:25,932 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-16 13:50:25,932 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-16 13:50:25,932 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-16 13:50:25,932 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-16 13:50:25,932 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-16 13:50:25,932 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-16 13:50:25,932 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-16 13:50:25,933 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-16 13:50:25,933 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-16 13:50:25,933 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 -> 06625eaf591a62e295090a882d83c1e11aaafca7ac8895e7d4adcf51d5b26e02 [2025-03-16 13:50:26,121 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-16 13:50:26,131 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-16 13:50:26,132 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-16 13:50:26,133 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-16 13:50:26,133 INFO L274 PluginConnector]: CDTParser initialized [2025-03-16 13:50:26,134 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/array-patterns/array8_pattern.c [2025-03-16 13:50:27,208 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/24eee8b68/337a7785cb6c4ddd812939d085f7be88/FLAG110377b44 [2025-03-16 13:50:27,402 INFO L384 CDTParser]: Found 1 translation units. [2025-03-16 13:50:27,402 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/array-patterns/array8_pattern.c [2025-03-16 13:50:27,408 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/24eee8b68/337a7785cb6c4ddd812939d085f7be88/FLAG110377b44 [2025-03-16 13:50:27,442 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/24eee8b68/337a7785cb6c4ddd812939d085f7be88 [2025-03-16 13:50:27,444 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-16 13:50:27,446 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-16 13:50:27,447 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-16 13:50:27,447 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-16 13:50:27,450 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-16 13:50:27,451 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.03 01:50:27" (1/1) ... [2025-03-16 13:50:27,451 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@51f6dd80 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:50:27, skipping insertion in model container [2025-03-16 13:50:27,451 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.03 01:50:27" (1/1) ... [2025-03-16 13:50:27,464 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-16 13:50:27,560 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/array8_pattern.c[1321,1334] [2025-03-16 13:50:27,579 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-16 13:50:27,586 INFO L200 MainTranslator]: Completed pre-run [2025-03-16 13:50:27,593 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/array8_pattern.c[1321,1334] [2025-03-16 13:50:27,602 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-16 13:50:27,614 INFO L204 MainTranslator]: Completed translation [2025-03-16 13:50:27,614 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:50:27 WrapperNode [2025-03-16 13:50:27,614 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-16 13:50:27,616 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-16 13:50:27,616 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-16 13:50:27,616 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-16 13:50:27,621 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:50:27" (1/1) ... [2025-03-16 13:50:27,626 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:50:27" (1/1) ... [2025-03-16 13:50:27,639 INFO L138 Inliner]: procedures = 16, calls = 23, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 76 [2025-03-16 13:50:27,640 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-16 13:50:27,641 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-16 13:50:27,642 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-16 13:50:27,642 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-16 13:50:27,646 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:50:27" (1/1) ... [2025-03-16 13:50:27,647 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:50:27" (1/1) ... [2025-03-16 13:50:27,648 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:50:27" (1/1) ... [2025-03-16 13:50:27,661 INFO L175 MemorySlicer]: Split 9 memory accesses to 3 slices as follows [2, 4, 3]. 44 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-16 13:50:27,662 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:50:27" (1/1) ... [2025-03-16 13:50:27,662 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:50:27" (1/1) ... [2025-03-16 13:50:27,666 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:50:27" (1/1) ... [2025-03-16 13:50:27,667 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:50:27" (1/1) ... [2025-03-16 13:50:27,667 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:50:27" (1/1) ... [2025-03-16 13:50:27,671 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:50:27" (1/1) ... [2025-03-16 13:50:27,672 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-16 13:50:27,672 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-16 13:50:27,672 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-16 13:50:27,673 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-16 13:50:27,673 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:50:27" (1/1) ... [2025-03-16 13:50:27,677 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-16 13:50:27,689 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:50:27,710 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2025-03-16 13:50:27,717 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2025-03-16 13:50:27,737 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-16 13:50:27,738 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2025-03-16 13:50:27,738 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2025-03-16 13:50:27,738 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-16 13:50:27,739 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2025-03-16 13:50:27,739 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2025-03-16 13:50:27,739 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2025-03-16 13:50:27,739 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2025-03-16 13:50:27,739 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2025-03-16 13:50:27,739 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2025-03-16 13:50:27,740 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-16 13:50:27,740 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-16 13:50:27,740 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2025-03-16 13:50:27,740 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2025-03-16 13:50:27,740 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2025-03-16 13:50:27,740 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2025-03-16 13:50:27,808 INFO L256 CfgBuilder]: Building ICFG [2025-03-16 13:50:27,810 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-16 13:50:27,925 INFO L1322 $ProcedureCfgBuilder]: dead code at ProgramPoint L44: 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-16 13:50:27,930 INFO L? ?]: Removed 12 outVars from TransFormulas that were not future-live. [2025-03-16 13:50:27,930 INFO L307 CfgBuilder]: Performing block encoding [2025-03-16 13:50:27,936 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-16 13:50:27,936 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-16 13:50:27,936 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.03 01:50:27 BoogieIcfgContainer [2025-03-16 13:50:27,936 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-16 13:50:27,938 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-16 13:50:27,938 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-16 13:50:27,941 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-16 13:50:27,941 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 16.03 01:50:27" (1/3) ... [2025-03-16 13:50:27,941 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@77f7a70e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.03 01:50:27, skipping insertion in model container [2025-03-16 13:50:27,942 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:50:27" (2/3) ... [2025-03-16 13:50:27,942 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@77f7a70e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.03 01:50:27, skipping insertion in model container [2025-03-16 13:50:27,942 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.03 01:50:27" (3/3) ... [2025-03-16 13:50:27,943 INFO L128 eAbstractionObserver]: Analyzing ICFG array8_pattern.c [2025-03-16 13:50:27,952 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-16 13:50:27,953 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG array8_pattern.c that has 2 procedures, 23 locations, 1 initial locations, 3 loop locations, and 1 error locations. [2025-03-16 13:50:27,991 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-16 13:50:27,998 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;@5045ab15, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-16 13:50:27,998 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-16 13:50:28,001 INFO L276 IsEmpty]: Start isEmpty. Operand has 23 states, 18 states have (on average 1.4444444444444444) internal successors, (26), 19 states have internal predecessors, (26), 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-16 13:50:28,004 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2025-03-16 13:50:28,004 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:50:28,005 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:50:28,005 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:50:28,008 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:50:28,008 INFO L85 PathProgramCache]: Analyzing trace with hash -1029332363, now seen corresponding path program 1 times [2025-03-16 13:50:28,013 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:50:28,013 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [801796403] [2025-03-16 13:50:28,013 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 13:50:28,014 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:50:28,071 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 13 statements into 1 equivalence classes. [2025-03-16 13:50:28,084 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 13 of 13 statements. [2025-03-16 13:50:28,084 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:50:28,085 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:50:28,116 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-16 13:50:28,117 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:50:28,117 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [801796403] [2025-03-16 13:50:28,117 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [801796403] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 13:50:28,118 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 13:50:28,118 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2025-03-16 13:50:28,119 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [600359322] [2025-03-16 13:50:28,119 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 13:50:28,121 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-03-16 13:50:28,122 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:50:28,133 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-03-16 13:50:28,133 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-16 13:50:28,135 INFO L87 Difference]: Start difference. First operand has 23 states, 18 states have (on average 1.4444444444444444) internal successors, (26), 19 states have internal predecessors, (26), 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 5.5) internal successors, (11), 2 states have internal predecessors, (11), 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-16 13:50:28,147 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:50:28,148 INFO L93 Difference]: Finished difference Result 44 states and 59 transitions. [2025-03-16 13:50:28,148 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-03-16 13:50:28,149 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 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 13 [2025-03-16 13:50:28,149 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:50:28,153 INFO L225 Difference]: With dead ends: 44 [2025-03-16 13:50:28,153 INFO L226 Difference]: Without dead ends: 19 [2025-03-16 13:50:28,156 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-16 13:50:28,158 INFO L435 NwaCegarLoop]: 27 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, 27 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 13:50:28,159 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 13:50:28,169 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states. [2025-03-16 13:50:28,179 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 19. [2025-03-16 13:50:28,180 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 19 states, 15 states have (on average 1.2666666666666666) internal successors, (19), 15 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-16 13:50:28,182 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 23 transitions. [2025-03-16 13:50:28,184 INFO L78 Accepts]: Start accepts. Automaton has 19 states and 23 transitions. Word has length 13 [2025-03-16 13:50:28,185 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:50:28,185 INFO L471 AbstractCegarLoop]: Abstraction has 19 states and 23 transitions. [2025-03-16 13:50:28,185 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 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-16 13:50:28,185 INFO L276 IsEmpty]: Start isEmpty. Operand 19 states and 23 transitions. [2025-03-16 13:50:28,186 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2025-03-16 13:50:28,187 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:50:28,187 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-16 13:50:28,187 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-03-16 13:50:28,187 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:50:28,188 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:50:28,188 INFO L85 PathProgramCache]: Analyzing trace with hash -10987556, now seen corresponding path program 1 times [2025-03-16 13:50:28,188 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:50:28,188 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1476351724] [2025-03-16 13:50:28,188 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 13:50:28,188 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:50:28,203 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 22 statements into 1 equivalence classes. [2025-03-16 13:50:28,248 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 22 of 22 statements. [2025-03-16 13:50:28,249 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:50:28,249 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:50:28,543 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-03-16 13:50:28,544 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:50:28,544 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1476351724] [2025-03-16 13:50:28,544 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1476351724] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:50:28,544 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1797490449] [2025-03-16 13:50:28,544 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 13:50:28,544 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:50:28,544 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:50:28,548 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:50:28,551 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-03-16 13:50:28,592 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 22 statements into 1 equivalence classes. [2025-03-16 13:50:28,609 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 22 of 22 statements. [2025-03-16 13:50:28,610 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:50:28,610 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:50:28,613 INFO L256 TraceCheckSpWp]: Trace formula consists of 102 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-16 13:50:28,616 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:50:28,709 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 13:50:28,710 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-16 13:50:28,710 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1797490449] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 13:50:28,711 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-16 13:50:28,711 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [7] total 11 [2025-03-16 13:50:28,711 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1689594989] [2025-03-16 13:50:28,711 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 13:50:28,711 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-03-16 13:50:28,711 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:50:28,712 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-16 13:50:28,712 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=86, Unknown=0, NotChecked=0, Total=110 [2025-03-16 13:50:28,712 INFO L87 Difference]: Start difference. First operand 19 states and 23 transitions. Second operand has 6 states, 6 states have (on average 3.0) internal successors, (18), 6 states have internal predecessors, (18), 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-16 13:50:28,758 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:50:28,758 INFO L93 Difference]: Finished difference Result 45 states and 52 transitions. [2025-03-16 13:50:28,758 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-16 13:50:28,759 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 3.0) internal successors, (18), 6 states have internal predecessors, (18), 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 22 [2025-03-16 13:50:28,759 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:50:28,759 INFO L225 Difference]: With dead ends: 45 [2025-03-16 13:50:28,759 INFO L226 Difference]: Without dead ends: 24 [2025-03-16 13:50:28,759 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 28 GetRequests, 19 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=24, Invalid=86, Unknown=0, NotChecked=0, Total=110 [2025-03-16 13:50:28,760 INFO L435 NwaCegarLoop]: 21 mSDtfsCounter, 2 mSDsluCounter, 37 mSDsCounter, 0 mSdLazyCounter, 30 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 58 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 30 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 13:50:28,760 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 58 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 30 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 13:50:28,760 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2025-03-16 13:50:28,762 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 20. [2025-03-16 13:50:28,762 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 16 states have (on average 1.25) internal successors, (20), 16 states have internal predecessors, (20), 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-16 13:50:28,765 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 24 transitions. [2025-03-16 13:50:28,765 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 24 transitions. Word has length 22 [2025-03-16 13:50:28,766 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:50:28,766 INFO L471 AbstractCegarLoop]: Abstraction has 20 states and 24 transitions. [2025-03-16 13:50:28,766 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 3.0) internal successors, (18), 6 states have internal predecessors, (18), 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-16 13:50:28,767 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 24 transitions. [2025-03-16 13:50:28,767 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2025-03-16 13:50:28,767 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:50:28,769 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-16 13:50:28,775 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2025-03-16 13:50:28,969 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:50:28,970 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:50:28,970 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:50:28,970 INFO L85 PathProgramCache]: Analyzing trace with hash 357806803, now seen corresponding path program 1 times [2025-03-16 13:50:28,970 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:50:28,970 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [204854757] [2025-03-16 13:50:28,970 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 13:50:28,971 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:50:28,977 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 23 statements into 1 equivalence classes. [2025-03-16 13:50:28,989 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 23 of 23 statements. [2025-03-16 13:50:28,989 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:50:28,990 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:50:29,096 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-16 13:50:29,097 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:50:29,097 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [204854757] [2025-03-16 13:50:29,097 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [204854757] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:50:29,097 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1469707882] [2025-03-16 13:50:29,097 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 13:50:29,097 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:50:29,097 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:50:29,099 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:50:29,101 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-03-16 13:50:29,135 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 23 statements into 1 equivalence classes. [2025-03-16 13:50:29,155 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 23 of 23 statements. [2025-03-16 13:50:29,155 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:50:29,156 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:50:29,156 INFO L256 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 4 conjuncts are in the unsatisfiable core [2025-03-16 13:50:29,157 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:50:29,193 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 4 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 13:50:29,193 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:50:29,238 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-16 13:50:29,238 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1469707882] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:50:29,238 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:50:29,238 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 5] total 9 [2025-03-16 13:50:29,238 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [590481934] [2025-03-16 13:50:29,238 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:50:29,238 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-03-16 13:50:29,238 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:50:29,239 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-16 13:50:29,239 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2025-03-16 13:50:29,239 INFO L87 Difference]: Start difference. First operand 20 states and 24 transitions. Second operand has 9 states, 9 states have (on average 3.5555555555555554) internal successors, (32), 9 states have internal predecessors, (32), 3 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2025-03-16 13:50:29,310 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:50:29,311 INFO L93 Difference]: Finished difference Result 28 states and 31 transitions. [2025-03-16 13:50:29,311 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-16 13:50:29,311 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 3.5555555555555554) internal successors, (32), 9 states have internal predecessors, (32), 3 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Word has length 23 [2025-03-16 13:50:29,311 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:50:29,312 INFO L225 Difference]: With dead ends: 28 [2025-03-16 13:50:29,312 INFO L226 Difference]: Without dead ends: 25 [2025-03-16 13:50:29,312 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 52 GetRequests, 40 SyntacticMatches, 2 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=39, Invalid=93, Unknown=0, NotChecked=0, Total=132 [2025-03-16 13:50:29,313 INFO L435 NwaCegarLoop]: 19 mSDtfsCounter, 15 mSDsluCounter, 59 mSDsCounter, 0 mSdLazyCounter, 49 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 78 SdHoareTripleChecker+Invalid, 57 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 49 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 13:50:29,313 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 78 Invalid, 57 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 49 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 13:50:29,314 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2025-03-16 13:50:29,317 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 25. [2025-03-16 13:50:29,317 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 25 states, 20 states have (on average 1.2) internal successors, (24), 20 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-16 13:50:29,317 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 28 transitions. [2025-03-16 13:50:29,318 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 28 transitions. Word has length 23 [2025-03-16 13:50:29,318 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:50:29,318 INFO L471 AbstractCegarLoop]: Abstraction has 25 states and 28 transitions. [2025-03-16 13:50:29,318 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 3.5555555555555554) internal successors, (32), 9 states have internal predecessors, (32), 3 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2025-03-16 13:50:29,318 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 28 transitions. [2025-03-16 13:50:29,318 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2025-03-16 13:50:29,318 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:50:29,319 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, 1] [2025-03-16 13:50:29,325 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2025-03-16 13:50:29,519 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2025-03-16 13:50:29,519 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:50:29,520 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:50:29,520 INFO L85 PathProgramCache]: Analyzing trace with hash -1792859242, now seen corresponding path program 1 times [2025-03-16 13:50:29,520 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:50:29,522 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [804042422] [2025-03-16 13:50:29,522 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 13:50:29,522 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:50:29,530 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 24 statements into 1 equivalence classes. [2025-03-16 13:50:29,548 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 24 of 24 statements. [2025-03-16 13:50:29,551 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:50:29,551 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 13:50:29,553 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [100293619] [2025-03-16 13:50:29,553 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 13:50:29,554 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:50:29,554 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:50:29,558 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:50:29,560 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-03-16 13:50:29,594 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 24 statements into 1 equivalence classes. [2025-03-16 13:50:29,608 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 24 of 24 statements. [2025-03-16 13:50:29,608 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:50:29,608 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:50:29,609 INFO L256 TraceCheckSpWp]: Trace formula consists of 118 conjuncts, 40 conjuncts are in the unsatisfiable core [2025-03-16 13:50:29,613 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:50:29,697 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 15 treesize of output 1 [2025-03-16 13:50:29,904 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-16 13:50:30,030 INFO L349 Elim1Store]: treesize reduction 16, result has 55.6 percent of original size [2025-03-16 13:50:30,031 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 41 treesize of output 33 [2025-03-16 13:50:30,153 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 17 treesize of output 9 [2025-03-16 13:50:30,188 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-16 13:50:30,188 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:50:30,308 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 33 treesize of output 31 [2025-03-16 13:50:30,311 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 51 treesize of output 49 [2025-03-16 13:50:30,565 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 35 treesize of output 33 [2025-03-16 13:50:30,569 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 51 treesize of output 49 [2025-03-16 13:50:30,636 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 3 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-03-16 13:50:30,636 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:50:30,636 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [804042422] [2025-03-16 13:50:30,637 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 13:50:30,637 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [100293619] [2025-03-16 13:50:30,637 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [100293619] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:50:30,637 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 13:50:30,637 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 13] total 29 [2025-03-16 13:50:30,637 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1032480362] [2025-03-16 13:50:30,637 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 13:50:30,637 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2025-03-16 13:50:30,637 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:50:30,638 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2025-03-16 13:50:30,638 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=126, Invalid=686, Unknown=0, NotChecked=0, Total=812 [2025-03-16 13:50:30,638 INFO L87 Difference]: Start difference. First operand 25 states and 28 transitions. Second operand has 29 states, 29 states have (on average 1.3103448275862069) internal successors, (38), 25 states have internal predecessors, (38), 3 states have call successors, (3), 2 states have call predecessors, (3), 4 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2025-03-16 13:50:31,147 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:50:31,147 INFO L93 Difference]: Finished difference Result 66 states and 77 transitions. [2025-03-16 13:50:31,148 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2025-03-16 13:50:31,148 INFO L78 Accepts]: Start accepts. Automaton has has 29 states, 29 states have (on average 1.3103448275862069) internal successors, (38), 25 states have internal predecessors, (38), 3 states have call successors, (3), 2 states have call predecessors, (3), 4 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) Word has length 24 [2025-03-16 13:50:31,148 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:50:31,148 INFO L225 Difference]: With dead ends: 66 [2025-03-16 13:50:31,148 INFO L226 Difference]: Without dead ends: 49 [2025-03-16 13:50:31,149 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 60 GetRequests, 18 SyntacticMatches, 1 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 472 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=326, Invalid=1480, Unknown=0, NotChecked=0, Total=1806 [2025-03-16 13:50:31,150 INFO L435 NwaCegarLoop]: 16 mSDtfsCounter, 60 mSDsluCounter, 166 mSDsCounter, 0 mSdLazyCounter, 314 mSolverCounterSat, 20 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 60 SdHoareTripleChecker+Valid, 182 SdHoareTripleChecker+Invalid, 334 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 20 IncrementalHoareTripleChecker+Valid, 314 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-16 13:50:31,150 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [60 Valid, 182 Invalid, 334 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [20 Valid, 314 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-16 13:50:31,150 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2025-03-16 13:50:31,156 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 38. [2025-03-16 13:50:31,157 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 38 states, 31 states have (on average 1.1935483870967742) internal successors, (37), 31 states have internal predecessors, (37), 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-16 13:50:31,157 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 43 transitions. [2025-03-16 13:50:31,159 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 43 transitions. Word has length 24 [2025-03-16 13:50:31,159 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:50:31,159 INFO L471 AbstractCegarLoop]: Abstraction has 38 states and 43 transitions. [2025-03-16 13:50:31,159 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 29 states, 29 states have (on average 1.3103448275862069) internal successors, (38), 25 states have internal predecessors, (38), 3 states have call successors, (3), 2 states have call predecessors, (3), 4 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2025-03-16 13:50:31,159 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 43 transitions. [2025-03-16 13:50:31,159 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2025-03-16 13:50:31,159 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:50:31,159 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:50:31,167 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2025-03-16 13:50:31,360 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:50:31,360 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:50:31,360 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:50:31,360 INFO L85 PathProgramCache]: Analyzing trace with hash 255970099, now seen corresponding path program 2 times [2025-03-16 13:50:31,360 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:50:31,360 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [87533220] [2025-03-16 13:50:31,360 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 13:50:31,361 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:50:31,369 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 25 statements into 2 equivalence classes. [2025-03-16 13:50:31,382 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 25 of 25 statements. [2025-03-16 13:50:31,382 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 13:50:31,382 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:50:31,457 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-16 13:50:31,457 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:50:31,457 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [87533220] [2025-03-16 13:50:31,457 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [87533220] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:50:31,457 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [998940320] [2025-03-16 13:50:31,457 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 13:50:31,457 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:50:31,457 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:50:31,459 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:50:31,462 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2025-03-16 13:50:31,494 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 25 statements into 2 equivalence classes. [2025-03-16 13:50:31,506 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 25 of 25 statements. [2025-03-16 13:50:31,506 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 13:50:31,506 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:50:31,506 INFO L256 TraceCheckSpWp]: Trace formula consists of 123 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-03-16 13:50:31,507 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:50:31,551 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-16 13:50:31,552 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:50:31,591 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-16 13:50:31,592 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [998940320] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:50:31,592 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:50:31,592 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 11 [2025-03-16 13:50:31,592 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [158359397] [2025-03-16 13:50:31,592 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:50:31,592 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2025-03-16 13:50:31,592 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:50:31,592 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2025-03-16 13:50:31,593 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=75, Unknown=0, NotChecked=0, Total=110 [2025-03-16 13:50:31,593 INFO L87 Difference]: Start difference. First operand 38 states and 43 transitions. Second operand has 11 states, 11 states have (on average 2.5454545454545454) internal successors, (28), 11 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-16 13:50:31,646 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:50:31,646 INFO L93 Difference]: Finished difference Result 47 states and 52 transitions. [2025-03-16 13:50:31,646 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-16 13:50:31,646 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 2.5454545454545454) internal successors, (28), 11 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 25 [2025-03-16 13:50:31,647 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:50:31,647 INFO L225 Difference]: With dead ends: 47 [2025-03-16 13:50:31,647 INFO L226 Difference]: Without dead ends: 30 [2025-03-16 13:50:31,647 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 56 GetRequests, 43 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-16 13:50:31,648 INFO L435 NwaCegarLoop]: 19 mSDtfsCounter, 27 mSDsluCounter, 75 mSDsCounter, 0 mSdLazyCounter, 71 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 94 SdHoareTripleChecker+Invalid, 83 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 71 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 13:50:31,648 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 94 Invalid, 83 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 71 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 13:50:31,648 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2025-03-16 13:50:31,650 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 26. [2025-03-16 13:50:31,651 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 21 states have (on average 1.1904761904761905) internal successors, (25), 21 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-16 13:50:31,651 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 29 transitions. [2025-03-16 13:50:31,651 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 29 transitions. Word has length 25 [2025-03-16 13:50:31,651 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:50:31,651 INFO L471 AbstractCegarLoop]: Abstraction has 26 states and 29 transitions. [2025-03-16 13:50:31,651 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 2.5454545454545454) internal successors, (28), 11 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-16 13:50:31,651 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 29 transitions. [2025-03-16 13:50:31,651 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2025-03-16 13:50:31,651 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:50:31,652 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:50:31,659 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2025-03-16 13:50:31,852 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:50:31,852 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:50:31,852 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:50:31,853 INFO L85 PathProgramCache]: Analyzing trace with hash 431201485, now seen corresponding path program 3 times [2025-03-16 13:50:31,853 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:50:31,853 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1787168181] [2025-03-16 13:50:31,853 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 13:50:31,853 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:50:31,858 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 25 statements into 3 equivalence classes. [2025-03-16 13:50:31,869 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) and asserted 25 of 25 statements. [2025-03-16 13:50:31,870 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2025-03-16 13:50:31,870 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:50:31,926 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-16 13:50:31,926 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:50:31,926 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1787168181] [2025-03-16 13:50:31,926 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1787168181] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:50:31,926 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1773257232] [2025-03-16 13:50:31,926 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 13:50:31,926 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:50:31,926 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:50:31,928 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:50:31,931 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2025-03-16 13:50:31,961 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 25 statements into 3 equivalence classes. [2025-03-16 13:50:31,975 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) and asserted 25 of 25 statements. [2025-03-16 13:50:31,975 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2025-03-16 13:50:31,975 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:50:31,976 INFO L256 TraceCheckSpWp]: Trace formula consists of 129 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-03-16 13:50:31,977 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:50:32,016 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-16 13:50:32,016 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:50:32,056 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-16 13:50:32,057 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1773257232] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:50:32,057 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:50:32,057 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 11 [2025-03-16 13:50:32,057 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1895794225] [2025-03-16 13:50:32,057 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:50:32,057 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2025-03-16 13:50:32,057 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:50:32,058 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2025-03-16 13:50:32,058 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=75, Unknown=0, NotChecked=0, Total=110 [2025-03-16 13:50:32,058 INFO L87 Difference]: Start difference. First operand 26 states and 29 transitions. Second operand has 11 states, 11 states have (on average 2.5454545454545454) internal successors, (28), 11 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-16 13:50:32,115 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:50:32,115 INFO L93 Difference]: Finished difference Result 30 states and 33 transitions. [2025-03-16 13:50:32,116 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-03-16 13:50:32,116 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 2.5454545454545454) internal successors, (28), 11 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 25 [2025-03-16 13:50:32,116 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:50:32,116 INFO L225 Difference]: With dead ends: 30 [2025-03-16 13:50:32,116 INFO L226 Difference]: Without dead ends: 27 [2025-03-16 13:50:32,116 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 42 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-16 13:50:32,117 INFO L435 NwaCegarLoop]: 19 mSDtfsCounter, 21 mSDsluCounter, 81 mSDsCounter, 0 mSdLazyCounter, 76 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 100 SdHoareTripleChecker+Invalid, 83 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 76 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 13:50:32,117 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 100 Invalid, 83 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 76 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 13:50:32,117 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2025-03-16 13:50:32,122 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2025-03-16 13:50:32,122 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 22 states have internal predecessors, (26), 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-16 13:50:32,122 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 30 transitions. [2025-03-16 13:50:32,123 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 30 transitions. Word has length 25 [2025-03-16 13:50:32,123 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:50:32,123 INFO L471 AbstractCegarLoop]: Abstraction has 27 states and 30 transitions. [2025-03-16 13:50:32,123 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 2.5454545454545454) internal successors, (28), 11 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-16 13:50:32,123 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 30 transitions. [2025-03-16 13:50:32,123 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2025-03-16 13:50:32,123 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:50:32,123 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:50:32,132 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2025-03-16 13:50:32,323 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:50:32,324 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:50:32,325 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:50:32,325 INFO L85 PathProgramCache]: Analyzing trace with hash 482375900, now seen corresponding path program 4 times [2025-03-16 13:50:32,325 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:50:32,325 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [948941187] [2025-03-16 13:50:32,325 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 13:50:32,325 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:50:32,333 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 26 statements into 2 equivalence classes. [2025-03-16 13:50:32,357 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 26 of 26 statements. [2025-03-16 13:50:32,358 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-16 13:50:32,358 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 13:50:32,358 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1229783598] [2025-03-16 13:50:32,359 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 13:50:32,359 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:50:32,359 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:50:32,363 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:50:32,364 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2025-03-16 13:50:32,401 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 26 statements into 2 equivalence classes. [2025-03-16 13:50:32,436 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 26 of 26 statements. [2025-03-16 13:50:32,436 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-16 13:50:32,436 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:50:32,437 INFO L256 TraceCheckSpWp]: Trace formula consists of 134 conjuncts, 56 conjuncts are in the unsatisfiable core [2025-03-16 13:50:32,440 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:50:32,500 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 15 treesize of output 1 [2025-03-16 13:50:32,512 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 15 treesize of output 1 [2025-03-16 13:50:32,547 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 23 treesize of output 11 [2025-03-16 13:50:32,555 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 23 treesize of output 11 [2025-03-16 13:50:32,773 INFO L349 Elim1Store]: treesize reduction 24, result has 48.9 percent of original size [2025-03-16 13:50:32,773 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 28 treesize of output 38 [2025-03-16 13:50:32,908 INFO L349 Elim1Store]: treesize reduction 48, result has 23.8 percent of original size [2025-03-16 13:50:32,909 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 5 case distinctions, treesize of input 34 treesize of output 30 [2025-03-16 13:50:33,192 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:50:33,193 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 38 treesize of output 22 [2025-03-16 13:50:33,204 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:50:33,205 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 63 treesize of output 45 [2025-03-16 13:50:33,245 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 1 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 13:50:33,245 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:50:33,457 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:50:33,457 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [948941187] [2025-03-16 13:50:33,457 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 13:50:33,457 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1229783598] [2025-03-16 13:50:33,457 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1229783598] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:50:33,457 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 13:50:33,457 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2025-03-16 13:50:33,457 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1492244445] [2025-03-16 13:50:33,457 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 13:50:33,458 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2025-03-16 13:50:33,458 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:50:33,458 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2025-03-16 13:50:33,458 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=99, Invalid=453, Unknown=0, NotChecked=0, Total=552 [2025-03-16 13:50:33,458 INFO L87 Difference]: Start difference. First operand 27 states and 30 transitions. Second operand has 17 states, 17 states have (on average 1.2941176470588236) internal successors, (22), 16 states have internal predecessors, (22), 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-16 13:50:33,903 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:50:33,903 INFO L93 Difference]: Finished difference Result 57 states and 67 transitions. [2025-03-16 13:50:33,904 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2025-03-16 13:50:33,904 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 1.2941176470588236) internal successors, (22), 16 states have internal predecessors, (22), 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 26 [2025-03-16 13:50:33,904 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:50:33,905 INFO L225 Difference]: With dead ends: 57 [2025-03-16 13:50:33,905 INFO L226 Difference]: Without dead ends: 54 [2025-03-16 13:50:33,905 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 44 GetRequests, 12 SyntacticMatches, 2 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 224 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=159, Invalid=833, Unknown=0, NotChecked=0, Total=992 [2025-03-16 13:50:33,906 INFO L435 NwaCegarLoop]: 15 mSDtfsCounter, 39 mSDsluCounter, 127 mSDsCounter, 0 mSdLazyCounter, 301 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 142 SdHoareTripleChecker+Invalid, 303 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 301 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-03-16 13:50:33,906 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [41 Valid, 142 Invalid, 303 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 301 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-03-16 13:50:33,906 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2025-03-16 13:50:33,917 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 40. [2025-03-16 13:50:33,917 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 40 states, 33 states have (on average 1.2121212121212122) internal successors, (40), 33 states have internal predecessors, (40), 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-16 13:50:33,917 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 46 transitions. [2025-03-16 13:50:33,918 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 46 transitions. Word has length 26 [2025-03-16 13:50:33,918 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:50:33,918 INFO L471 AbstractCegarLoop]: Abstraction has 40 states and 46 transitions. [2025-03-16 13:50:33,918 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 1.2941176470588236) internal successors, (22), 16 states have internal predecessors, (22), 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-16 13:50:33,918 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 46 transitions. [2025-03-16 13:50:33,919 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2025-03-16 13:50:33,919 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:50:33,919 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:50:33,926 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2025-03-16 13:50:34,120 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:50:34,120 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:50:34,120 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:50:34,120 INFO L85 PathProgramCache]: Analyzing trace with hash -1325078563, now seen corresponding path program 1 times [2025-03-16 13:50:34,120 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:50:34,120 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1879811324] [2025-03-16 13:50:34,120 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 13:50:34,120 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:50:34,128 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 26 statements into 1 equivalence classes. [2025-03-16 13:50:34,144 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 26 of 26 statements. [2025-03-16 13:50:34,144 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:50:34,144 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 13:50:34,145 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2079110940] [2025-03-16 13:50:34,145 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 13:50:34,145 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:50:34,145 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:50:34,147 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:50:34,148 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2025-03-16 13:50:34,182 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 26 statements into 1 equivalence classes. [2025-03-16 13:50:34,194 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 26 of 26 statements. [2025-03-16 13:50:34,194 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:50:34,194 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:50:34,195 INFO L256 TraceCheckSpWp]: Trace formula consists of 131 conjuncts, 53 conjuncts are in the unsatisfiable core [2025-03-16 13:50:34,197 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:50:34,238 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 15 treesize of output 1 [2025-03-16 13:50:34,243 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 15 treesize of output 1 [2025-03-16 13:50:34,278 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 23 treesize of output 11 [2025-03-16 13:50:34,289 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 23 treesize of output 11 [2025-03-16 13:50:34,579 INFO L349 Elim1Store]: treesize reduction 64, result has 48.8 percent of original size [2025-03-16 13:50:34,579 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 1 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 10 case distinctions, treesize of input 42 treesize of output 82 [2025-03-16 13:50:35,102 INFO L349 Elim1Store]: treesize reduction 88, result has 40.9 percent of original size [2025-03-16 13:50:35,103 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 1 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 9 case distinctions, treesize of input 48 treesize of output 73 [2025-03-16 13:50:36,222 INFO L349 Elim1Store]: treesize reduction 288, result has 44.7 percent of original size [2025-03-16 13:50:36,223 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 13 select indices, 13 select index equivalence classes, 1 disjoint index pairs (out of 78 index pairs), introduced 13 new quantified variables, introduced 78 case distinctions, treesize of input 280 treesize of output 402 [2025-03-16 13:50:36,271 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:50:36,272 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 5 select indices, 5 select index equivalence classes, 1 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 10 case distinctions, treesize of input 184 treesize of output 214 [2025-03-16 13:50:49,025 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-16 13:50:49,025 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:50:49,477 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:50:49,477 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1879811324] [2025-03-16 13:50:49,477 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 13:50:49,477 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2079110940] [2025-03-16 13:50:49,478 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2079110940] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:50:49,478 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 13:50:49,478 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20] total 20 [2025-03-16 13:50:49,478 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1398037638] [2025-03-16 13:50:49,478 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 13:50:49,478 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2025-03-16 13:50:49,478 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:50:49,478 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2025-03-16 13:50:49,479 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=132, Invalid=680, Unknown=0, NotChecked=0, Total=812 [2025-03-16 13:50:49,479 INFO L87 Difference]: Start difference. First operand 40 states and 46 transitions. Second operand has 20 states, 20 states have (on average 1.1) internal successors, (22), 17 states have internal predecessors, (22), 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-16 13:50:50,039 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:50:50,039 INFO L93 Difference]: Finished difference Result 62 states and 71 transitions. [2025-03-16 13:50:50,039 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2025-03-16 13:50:50,039 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 1.1) internal successors, (22), 17 states have internal predecessors, (22), 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 26 [2025-03-16 13:50:50,039 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:50:50,040 INFO L225 Difference]: With dead ends: 62 [2025-03-16 13:50:50,040 INFO L226 Difference]: Without dead ends: 59 [2025-03-16 13:50:50,040 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 289 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=187, Invalid=1003, Unknown=0, NotChecked=0, Total=1190 [2025-03-16 13:50:50,041 INFO L435 NwaCegarLoop]: 18 mSDtfsCounter, 34 mSDsluCounter, 139 mSDsCounter, 0 mSdLazyCounter, 303 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 157 SdHoareTripleChecker+Invalid, 313 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 303 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-03-16 13:50:50,041 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [35 Valid, 157 Invalid, 313 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 303 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-03-16 13:50:50,041 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2025-03-16 13:50:50,050 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 48. [2025-03-16 13:50:50,050 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 39 states have (on average 1.205128205128205) internal successors, (47), 39 states have internal predecessors, (47), 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-16 13:50:50,050 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 55 transitions. [2025-03-16 13:50:50,050 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 55 transitions. Word has length 26 [2025-03-16 13:50:50,050 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:50:50,050 INFO L471 AbstractCegarLoop]: Abstraction has 48 states and 55 transitions. [2025-03-16 13:50:50,050 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 1.1) internal successors, (22), 17 states have internal predecessors, (22), 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-16 13:50:50,050 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 55 transitions. [2025-03-16 13:50:50,051 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2025-03-16 13:50:50,051 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:50:50,051 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, 1] [2025-03-16 13:50:50,058 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-16 13:50:50,251 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:50:50,251 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:50:50,252 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:50:50,252 INFO L85 PathProgramCache]: Analyzing trace with hash 2068782765, now seen corresponding path program 5 times [2025-03-16 13:50:50,252 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:50:50,252 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1456675889] [2025-03-16 13:50:50,252 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-16 13:50:50,252 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:50:50,257 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 27 statements into 3 equivalence classes. [2025-03-16 13:50:50,268 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 3 check-sat command(s) and asserted 27 of 27 statements. [2025-03-16 13:50:50,269 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 3 check-sat command(s) [2025-03-16 13:50:50,269 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:50:50,343 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-16 13:50:50,343 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:50:50,343 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1456675889] [2025-03-16 13:50:50,343 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1456675889] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:50:50,343 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1361873531] [2025-03-16 13:50:50,343 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-16 13:50:50,343 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:50:50,343 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:50:50,345 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:50:50,346 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2025-03-16 13:50:50,384 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 27 statements into 3 equivalence classes. [2025-03-16 13:50:50,398 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 3 check-sat command(s) and asserted 27 of 27 statements. [2025-03-16 13:50:50,399 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 3 check-sat command(s) [2025-03-16 13:50:50,399 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:50:50,401 INFO L256 TraceCheckSpWp]: Trace formula consists of 139 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-16 13:50:50,401 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:50:50,443 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-16 13:50:50,443 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:50:50,477 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-16 13:50:50,478 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1361873531] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:50:50,478 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:50:50,478 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 12 [2025-03-16 13:50:50,478 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [541268958] [2025-03-16 13:50:50,478 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:50:50,478 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2025-03-16 13:50:50,478 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:50:50,478 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2025-03-16 13:50:50,479 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=93, Unknown=0, NotChecked=0, Total=132 [2025-03-16 13:50:50,479 INFO L87 Difference]: Start difference. First operand 48 states and 55 transitions. Second operand has 12 states, 12 states have (on average 2.25) internal successors, (27), 12 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-16 13:50:50,549 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:50:50,549 INFO L93 Difference]: Finished difference Result 78 states and 89 transitions. [2025-03-16 13:50:50,550 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-16 13:50:50,550 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.25) internal successors, (27), 12 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 27 [2025-03-16 13:50:50,550 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:50:50,550 INFO L225 Difference]: With dead ends: 78 [2025-03-16 13:50:50,550 INFO L226 Difference]: Without dead ends: 70 [2025-03-16 13:50:50,550 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 64 GetRequests, 45 SyntacticMatches, 6 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 48 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=66, Invalid=144, Unknown=0, NotChecked=0, Total=210 [2025-03-16 13:50:50,551 INFO L435 NwaCegarLoop]: 19 mSDtfsCounter, 46 mSDsluCounter, 66 mSDsCounter, 0 mSdLazyCounter, 69 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 47 SdHoareTripleChecker+Valid, 85 SdHoareTripleChecker+Invalid, 93 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 69 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 13:50:50,551 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [47 Valid, 85 Invalid, 93 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 69 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 13:50:50,551 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 70 states. [2025-03-16 13:50:50,560 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 70 to 64. [2025-03-16 13:50:50,560 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 53 states have (on average 1.1886792452830188) internal successors, (63), 53 states have internal predecessors, (63), 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-16 13:50:50,561 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 73 transitions. [2025-03-16 13:50:50,561 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 73 transitions. Word has length 27 [2025-03-16 13:50:50,561 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:50:50,561 INFO L471 AbstractCegarLoop]: Abstraction has 64 states and 73 transitions. [2025-03-16 13:50:50,561 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 2.25) internal successors, (27), 12 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-16 13:50:50,561 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 73 transitions. [2025-03-16 13:50:50,561 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2025-03-16 13:50:50,561 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:50:50,561 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, 1] [2025-03-16 13:50:50,567 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2025-03-16 13:50:50,762 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,SelfDestructingSolverStorable8 [2025-03-16 13:50:50,762 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:50:50,762 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:50:50,762 INFO L85 PathProgramCache]: Analyzing trace with hash -1088978861, now seen corresponding path program 6 times [2025-03-16 13:50:50,762 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:50:50,762 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [176929366] [2025-03-16 13:50:50,762 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-16 13:50:50,762 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:50:50,767 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 27 statements into 4 equivalence classes. [2025-03-16 13:50:50,782 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) and asserted 27 of 27 statements. [2025-03-16 13:50:50,782 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2025-03-16 13:50:50,782 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:50:50,863 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 1 proven. 8 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-16 13:50:50,863 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:50:50,863 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [176929366] [2025-03-16 13:50:50,863 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [176929366] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:50:50,863 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1544499218] [2025-03-16 13:50:50,863 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-16 13:50:50,863 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:50:50,863 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:50:50,865 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:50:50,866 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2025-03-16 13:50:50,900 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 27 statements into 4 equivalence classes. [2025-03-16 13:50:50,914 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) and asserted 27 of 27 statements. [2025-03-16 13:50:50,914 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2025-03-16 13:50:50,914 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:50:50,914 INFO L256 TraceCheckSpWp]: Trace formula consists of 145 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-16 13:50:50,915 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:50:50,955 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-16 13:50:50,955 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:50:50,990 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-16 13:50:50,990 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1544499218] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:50:50,990 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:50:50,990 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 14 [2025-03-16 13:50:50,990 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [379060670] [2025-03-16 13:50:50,990 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:50:50,990 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2025-03-16 13:50:50,990 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:50:50,990 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2025-03-16 13:50:50,991 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=129, Unknown=0, NotChecked=0, Total=182 [2025-03-16 13:50:50,991 INFO L87 Difference]: Start difference. First operand 64 states and 73 transitions. Second operand has 14 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 14 states have internal predecessors, (31), 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-16 13:50:51,075 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:50:51,075 INFO L93 Difference]: Finished difference Result 73 states and 81 transitions. [2025-03-16 13:50:51,075 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-03-16 13:50:51,075 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 14 states have internal predecessors, (31), 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 27 [2025-03-16 13:50:51,075 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:50:51,076 INFO L225 Difference]: With dead ends: 73 [2025-03-16 13:50:51,076 INFO L226 Difference]: Without dead ends: 70 [2025-03-16 13:50:51,076 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 64 GetRequests, 43 SyntacticMatches, 6 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 89 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=77, Invalid=195, Unknown=0, NotChecked=0, Total=272 [2025-03-16 13:50:51,076 INFO L435 NwaCegarLoop]: 25 mSDtfsCounter, 28 mSDsluCounter, 107 mSDsCounter, 0 mSdLazyCounter, 137 mSolverCounterSat, 23 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 132 SdHoareTripleChecker+Invalid, 160 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 23 IncrementalHoareTripleChecker+Valid, 137 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 13:50:51,077 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [29 Valid, 132 Invalid, 160 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [23 Valid, 137 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 13:50:51,077 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 70 states. [2025-03-16 13:50:51,090 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 70 to 53. [2025-03-16 13:50:51,091 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 53 states, 44 states have (on average 1.1818181818181819) internal successors, (52), 44 states have internal predecessors, (52), 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-16 13:50:51,092 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 60 transitions. [2025-03-16 13:50:51,093 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 60 transitions. Word has length 27 [2025-03-16 13:50:51,093 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:50:51,093 INFO L471 AbstractCegarLoop]: Abstraction has 53 states and 60 transitions. [2025-03-16 13:50:51,093 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 14 states have internal predecessors, (31), 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-16 13:50:51,093 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 60 transitions. [2025-03-16 13:50:51,093 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2025-03-16 13:50:51,093 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:50:51,093 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, 1] [2025-03-16 13:50:51,100 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2025-03-16 13:50:51,293 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2025-03-16 13:50:51,294 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:50:51,294 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:50:51,295 INFO L85 PathProgramCache]: Analyzing trace with hash 601425430, now seen corresponding path program 7 times [2025-03-16 13:50:51,295 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:50:51,295 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [992606117] [2025-03-16 13:50:51,295 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-16 13:50:51,295 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:50:51,299 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-16 13:50:51,314 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-16 13:50:51,314 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:50:51,314 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 13:50:51,315 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1694626836] [2025-03-16 13:50:51,315 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-16 13:50:51,315 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:50:51,315 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:50:51,317 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:50:51,318 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2025-03-16 13:50:51,357 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-16 13:50:51,371 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-16 13:50:51,371 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:50:51,371 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:50:51,372 INFO L256 TraceCheckSpWp]: Trace formula consists of 150 conjuncts, 60 conjuncts are in the unsatisfiable core [2025-03-16 13:50:51,375 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:50:51,418 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 15 treesize of output 1 [2025-03-16 13:50:51,426 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 15 treesize of output 1 [2025-03-16 13:50:51,454 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 23 treesize of output 11 [2025-03-16 13:50:51,464 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 23 treesize of output 11 [2025-03-16 13:50:51,499 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 0 case distinctions, treesize of input 30 treesize of output 21 [2025-03-16 13:50:51,506 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 0 case distinctions, treesize of input 30 treesize of output 21 [2025-03-16 13:50:51,699 INFO L349 Elim1Store]: treesize reduction 36, result has 48.6 percent of original size [2025-03-16 13:50:51,699 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 6 case distinctions, treesize of input 35 treesize of output 52 [2025-03-16 13:50:51,844 INFO L349 Elim1Store]: treesize reduction 54, result has 51.8 percent of original size [2025-03-16 13:50:51,844 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 9 case distinctions, treesize of input 56 treesize of output 76 [2025-03-16 13:50:52,534 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:50:52,534 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 224 treesize of output 182 [2025-03-16 13:50:52,557 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:50:52,558 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 5 select indices, 5 select index equivalence classes, 3 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 10 case distinctions, treesize of input 158 treesize of output 150 [2025-03-16 13:50:52,809 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 1 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 13:50:52,809 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:50:53,079 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:50:53,079 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [992606117] [2025-03-16 13:50:53,079 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 13:50:53,079 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1694626836] [2025-03-16 13:50:53,079 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1694626836] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:50:53,079 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 13:50:53,079 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19] total 19 [2025-03-16 13:50:53,079 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [655182015] [2025-03-16 13:50:53,079 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 13:50:53,079 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2025-03-16 13:50:53,079 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:50:53,080 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2025-03-16 13:50:53,080 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=113, Invalid=589, Unknown=0, NotChecked=0, Total=702 [2025-03-16 13:50:53,080 INFO L87 Difference]: Start difference. First operand 53 states and 60 transitions. Second operand has 19 states, 19 states have (on average 1.263157894736842) internal successors, (24), 18 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-16 13:50:53,402 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:50:53,402 INFO L93 Difference]: Finished difference Result 75 states and 85 transitions. [2025-03-16 13:50:53,402 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2025-03-16 13:50:53,402 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 1.263157894736842) internal successors, (24), 18 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) Word has length 28 [2025-03-16 13:50:53,402 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:50:53,403 INFO L225 Difference]: With dead ends: 75 [2025-03-16 13:50:53,403 INFO L226 Difference]: Without dead ends: 72 [2025-03-16 13:50:53,403 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 44 GetRequests, 12 SyntacticMatches, 2 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 246 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=138, Invalid=854, Unknown=0, NotChecked=0, Total=992 [2025-03-16 13:50:53,403 INFO L435 NwaCegarLoop]: 23 mSDtfsCounter, 36 mSDsluCounter, 151 mSDsCounter, 0 mSdLazyCounter, 333 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 40 SdHoareTripleChecker+Valid, 174 SdHoareTripleChecker+Invalid, 338 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 333 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-16 13:50:53,404 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [40 Valid, 174 Invalid, 338 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 333 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-16 13:50:53,404 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2025-03-16 13:50:53,415 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 65. [2025-03-16 13:50:53,415 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 65 states, 54 states have (on average 1.1851851851851851) internal successors, (64), 54 states have internal predecessors, (64), 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-16 13:50:53,415 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 65 states to 65 states and 74 transitions. [2025-03-16 13:50:53,415 INFO L78 Accepts]: Start accepts. Automaton has 65 states and 74 transitions. Word has length 28 [2025-03-16 13:50:53,415 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:50:53,415 INFO L471 AbstractCegarLoop]: Abstraction has 65 states and 74 transitions. [2025-03-16 13:50:53,415 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 1.263157894736842) internal successors, (24), 18 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-16 13:50:53,416 INFO L276 IsEmpty]: Start isEmpty. Operand 65 states and 74 transitions. [2025-03-16 13:50:53,416 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2025-03-16 13:50:53,416 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:50:53,416 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, 1] [2025-03-16 13:50:53,422 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2025-03-16 13:50:53,620 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,SelfDestructingSolverStorable10 [2025-03-16 13:50:53,622 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:50:53,622 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:50:53,622 INFO L85 PathProgramCache]: Analyzing trace with hash 404911925, now seen corresponding path program 2 times [2025-03-16 13:50:53,622 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:50:53,622 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [37177451] [2025-03-16 13:50:53,622 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 13:50:53,622 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:50:53,630 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 28 statements into 2 equivalence classes. [2025-03-16 13:50:53,653 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 28 of 28 statements. [2025-03-16 13:50:53,654 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 13:50:53,654 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 13:50:53,654 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2116059623] [2025-03-16 13:50:53,654 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 13:50:53,654 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:50:53,655 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:50:53,657 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:50:53,658 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2025-03-16 13:50:53,696 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 28 statements into 2 equivalence classes. [2025-03-16 13:50:53,709 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 28 of 28 statements. [2025-03-16 13:50:53,709 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 13:50:53,709 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:50:53,710 INFO L256 TraceCheckSpWp]: Trace formula consists of 147 conjuncts, 51 conjuncts are in the unsatisfiable core [2025-03-16 13:50:53,712 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:50:53,731 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 15 treesize of output 1 [2025-03-16 13:50:53,737 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 15 treesize of output 1 [2025-03-16 13:50:53,756 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 23 treesize of output 11 [2025-03-16 13:50:53,761 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 23 treesize of output 11 [2025-03-16 13:50:53,793 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 0 case distinctions, treesize of input 30 treesize of output 21 [2025-03-16 13:50:53,802 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 0 case distinctions, treesize of input 30 treesize of output 21 [2025-03-16 13:50:53,987 INFO L349 Elim1Store]: treesize reduction 36, result has 48.6 percent of original size [2025-03-16 13:50:53,988 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 6 case distinctions, treesize of input 35 treesize of output 52 [2025-03-16 13:50:54,192 INFO L349 Elim1Store]: treesize reduction 54, result has 38.6 percent of original size [2025-03-16 13:50:54,192 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 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 41 treesize of output 43 [2025-03-16 13:50:54,717 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:50:54,717 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 202 treesize of output 168 [2025-03-16 13:50:54,729 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:50:54,729 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 141 treesize of output 111 [2025-03-16 13:50:55,098 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-16 13:50:55,098 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:51:02,092 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:51:02,092 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [37177451] [2025-03-16 13:51:02,092 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 13:51:02,092 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2116059623] [2025-03-16 13:51:02,092 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2116059623] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:51:02,092 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 13:51:02,092 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2025-03-16 13:51:02,093 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [889153007] [2025-03-16 13:51:02,093 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 13:51:02,093 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-03-16 13:51:02,093 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:51:02,093 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-03-16 13:51:02,093 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=96, Invalid=455, Unknown=1, NotChecked=0, Total=552 [2025-03-16 13:51:02,093 INFO L87 Difference]: Start difference. First operand 65 states and 74 transitions. Second operand has 16 states, 16 states have (on average 1.5) internal successors, (24), 16 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-16 13:51:02,468 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:51:02,469 INFO L93 Difference]: Finished difference Result 79 states and 90 transitions. [2025-03-16 13:51:02,469 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2025-03-16 13:51:02,470 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 1.5) internal successors, (24), 16 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) Word has length 28 [2025-03-16 13:51:02,470 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:51:02,470 INFO L225 Difference]: With dead ends: 79 [2025-03-16 13:51:02,470 INFO L226 Difference]: Without dead ends: 76 [2025-03-16 13:51:02,470 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 15 SyntacticMatches, 2 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 119 ImplicationChecksByTransitivity, 7.5s TimeCoverageRelationStatistics Valid=133, Invalid=568, Unknown=1, NotChecked=0, Total=702 [2025-03-16 13:51:02,471 INFO L435 NwaCegarLoop]: 30 mSDtfsCounter, 18 mSDsluCounter, 149 mSDsCounter, 0 mSdLazyCounter, 247 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 179 SdHoareTripleChecker+Invalid, 256 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 247 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-16 13:51:02,471 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [20 Valid, 179 Invalid, 256 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 247 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-16 13:51:02,471 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2025-03-16 13:51:02,482 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 65. [2025-03-16 13:51:02,482 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 65 states, 54 states have (on average 1.1851851851851851) internal successors, (64), 54 states have internal predecessors, (64), 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-16 13:51:02,482 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 65 states to 65 states and 74 transitions. [2025-03-16 13:51:02,483 INFO L78 Accepts]: Start accepts. Automaton has 65 states and 74 transitions. Word has length 28 [2025-03-16 13:51:02,483 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:51:02,483 INFO L471 AbstractCegarLoop]: Abstraction has 65 states and 74 transitions. [2025-03-16 13:51:02,483 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 1.5) internal successors, (24), 16 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-16 13:51:02,483 INFO L276 IsEmpty]: Start isEmpty. Operand 65 states and 74 transitions. [2025-03-16 13:51:02,483 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2025-03-16 13:51:02,483 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:51:02,483 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, 1] [2025-03-16 13:51:02,489 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-16 13:51:02,684 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,SelfDestructingSolverStorable11 [2025-03-16 13:51:02,684 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:51:02,685 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:51:02,685 INFO L85 PathProgramCache]: Analyzing trace with hash 1464350899, now seen corresponding path program 8 times [2025-03-16 13:51:02,685 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:51:02,685 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [330844992] [2025-03-16 13:51:02,685 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 13:51:02,685 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:51:02,689 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 29 statements into 2 equivalence classes. [2025-03-16 13:51:02,694 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 29 of 29 statements. [2025-03-16 13:51:02,694 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 13:51:02,694 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:51:02,786 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-16 13:51:02,786 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:51:02,786 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [330844992] [2025-03-16 13:51:02,786 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [330844992] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:51:02,786 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1572022792] [2025-03-16 13:51:02,786 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 13:51:02,786 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:51:02,786 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:51:02,791 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:51:02,792 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2025-03-16 13:51:02,831 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 29 statements into 2 equivalence classes. [2025-03-16 13:51:02,843 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 29 of 29 statements. [2025-03-16 13:51:02,843 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 13:51:02,843 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:51:02,843 INFO L256 TraceCheckSpWp]: Trace formula consists of 155 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-03-16 13:51:02,844 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:51:02,894 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-16 13:51:02,895 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:51:02,955 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-16 13:51:02,955 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1572022792] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:51:02,955 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:51:02,955 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 11] total 17 [2025-03-16 13:51:02,955 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [627220558] [2025-03-16 13:51:02,955 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:51:02,955 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2025-03-16 13:51:02,955 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:51:02,956 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2025-03-16 13:51:02,956 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=75, Invalid=197, Unknown=0, NotChecked=0, Total=272 [2025-03-16 13:51:02,956 INFO L87 Difference]: Start difference. First operand 65 states and 74 transitions. Second operand has 17 states, 17 states have (on average 2.0) internal successors, (34), 17 states have internal predecessors, (34), 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-16 13:51:03,084 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:51:03,084 INFO L93 Difference]: Finished difference Result 107 states and 122 transitions. [2025-03-16 13:51:03,085 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2025-03-16 13:51:03,085 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 2.0) internal successors, (34), 17 states have internal predecessors, (34), 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 29 [2025-03-16 13:51:03,085 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:51:03,085 INFO L225 Difference]: With dead ends: 107 [2025-03-16 13:51:03,085 INFO L226 Difference]: Without dead ends: 98 [2025-03-16 13:51:03,086 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 45 SyntacticMatches, 7 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 174 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=145, Invalid=361, Unknown=0, NotChecked=0, Total=506 [2025-03-16 13:51:03,086 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 68 mSDsluCounter, 114 mSDsCounter, 0 mSdLazyCounter, 117 mSolverCounterSat, 28 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 69 SdHoareTripleChecker+Valid, 138 SdHoareTripleChecker+Invalid, 145 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 28 IncrementalHoareTripleChecker+Valid, 117 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 13:51:03,086 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [69 Valid, 138 Invalid, 145 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [28 Valid, 117 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 13:51:03,086 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2025-03-16 13:51:03,109 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 88. [2025-03-16 13:51:03,109 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 88 states, 73 states have (on average 1.1917808219178083) internal successors, (87), 73 states have internal predecessors, (87), 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-16 13:51:03,110 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 101 transitions. [2025-03-16 13:51:03,110 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 101 transitions. Word has length 29 [2025-03-16 13:51:03,110 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:51:03,110 INFO L471 AbstractCegarLoop]: Abstraction has 88 states and 101 transitions. [2025-03-16 13:51:03,110 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 2.0) internal successors, (34), 17 states have internal predecessors, (34), 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-16 13:51:03,110 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 101 transitions. [2025-03-16 13:51:03,111 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2025-03-16 13:51:03,112 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:51:03,112 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, 1] [2025-03-16 13:51:03,119 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-16 13:51:03,312 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,SelfDestructingSolverStorable12 [2025-03-16 13:51:03,312 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:51:03,313 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:51:03,313 INFO L85 PathProgramCache]: Analyzing trace with hash 83225052, now seen corresponding path program 9 times [2025-03-16 13:51:03,313 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:51:03,313 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1982749483] [2025-03-16 13:51:03,313 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 13:51:03,313 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:51:03,318 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 30 statements into 4 equivalence classes. [2025-03-16 13:51:03,358 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) and asserted 30 of 30 statements. [2025-03-16 13:51:03,358 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2025-03-16 13:51:03,358 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 13:51:03,360 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1449479942] [2025-03-16 13:51:03,360 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 13:51:03,360 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:51:03,360 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:51:03,363 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:51:03,365 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2025-03-16 13:51:03,412 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 30 statements into 4 equivalence classes. [2025-03-16 13:51:03,439 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) and asserted 30 of 30 statements. [2025-03-16 13:51:03,439 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2025-03-16 13:51:03,439 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:51:03,444 WARN L254 TraceCheckSpWp]: Trace formula consists of 166 conjuncts, 85 conjuncts are in the unsatisfiable core [2025-03-16 13:51:03,447 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:51:03,479 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 15 treesize of output 1 [2025-03-16 13:51:03,485 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 15 treesize of output 1 [2025-03-16 13:51:03,509 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 23 treesize of output 11 [2025-03-16 13:51:03,519 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 23 treesize of output 11 [2025-03-16 13:51:03,556 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 0 case distinctions, treesize of input 30 treesize of output 21 [2025-03-16 13:51:03,567 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 0 case distinctions, treesize of input 30 treesize of output 21 [2025-03-16 13:51:03,611 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 0 case distinctions, treesize of input 37 treesize of output 31 [2025-03-16 13:51:03,627 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 0 case distinctions, treesize of input 37 treesize of output 31 [2025-03-16 13:51:04,056 INFO L349 Elim1Store]: treesize reduction 128, result has 48.6 percent of original size [2025-03-16 13:51:04,057 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 8 select indices, 8 select index equivalence classes, 6 disjoint index pairs (out of 28 index pairs), introduced 8 new quantified variables, introduced 36 case distinctions, treesize of input 70 treesize of output 154 [2025-03-16 13:51:04,552 INFO L349 Elim1Store]: treesize reduction 272, result has 17.3 percent of original size [2025-03-16 13:51:04,552 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 76 treesize of output 90 [2025-03-16 13:51:05,252 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:51:05,253 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 144 treesize of output 76 [2025-03-16 13:51:05,273 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:51:05,274 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 8 select indices, 8 select index equivalence classes, 6 disjoint index pairs (out of 28 index pairs), introduced 8 new quantified variables, introduced 28 case distinctions, treesize of input 84 treesize of output 68 [2025-03-16 13:51:05,359 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-16 13:51:05,359 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:51:05,869 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:51:05,869 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1982749483] [2025-03-16 13:51:05,869 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 13:51:05,869 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1449479942] [2025-03-16 13:51:05,869 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1449479942] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:51:05,869 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 13:51:05,869 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [24] total 24 [2025-03-16 13:51:05,869 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1706603266] [2025-03-16 13:51:05,869 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 13:51:05,869 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2025-03-16 13:51:05,869 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:51:05,870 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2025-03-16 13:51:05,870 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=171, Invalid=951, Unknown=0, NotChecked=0, Total=1122 [2025-03-16 13:51:05,870 INFO L87 Difference]: Start difference. First operand 88 states and 101 transitions. Second operand has 24 states, 24 states have (on average 1.0833333333333333) internal successors, (26), 21 states have internal predecessors, (26), 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-16 13:51:06,409 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:51:06,409 INFO L93 Difference]: Finished difference Result 114 states and 132 transitions. [2025-03-16 13:51:06,410 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2025-03-16 13:51:06,410 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 24 states have (on average 1.0833333333333333) internal successors, (26), 21 states have internal predecessors, (26), 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 30 [2025-03-16 13:51:06,410 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:51:06,410 INFO L225 Difference]: With dead ends: 114 [2025-03-16 13:51:06,410 INFO L226 Difference]: Without dead ends: 103 [2025-03-16 13:51:06,411 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 45 GetRequests, 9 SyntacticMatches, 1 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 381 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=186, Invalid=1146, Unknown=0, NotChecked=0, Total=1332 [2025-03-16 13:51:06,411 INFO L435 NwaCegarLoop]: 23 mSDtfsCounter, 26 mSDsluCounter, 231 mSDsCounter, 0 mSdLazyCounter, 572 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 254 SdHoareTripleChecker+Invalid, 576 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 572 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2025-03-16 13:51:06,411 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [29 Valid, 254 Invalid, 576 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 572 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2025-03-16 13:51:06,412 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 103 states. [2025-03-16 13:51:06,428 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 103 to 99. [2025-03-16 13:51:06,428 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 99 states, 82 states have (on average 1.1951219512195121) internal successors, (98), 82 states have internal predecessors, (98), 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-16 13:51:06,429 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 114 transitions. [2025-03-16 13:51:06,429 INFO L78 Accepts]: Start accepts. Automaton has 99 states and 114 transitions. Word has length 30 [2025-03-16 13:51:06,429 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:51:06,429 INFO L471 AbstractCegarLoop]: Abstraction has 99 states and 114 transitions. [2025-03-16 13:51:06,429 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 24 states have (on average 1.0833333333333333) internal successors, (26), 21 states have internal predecessors, (26), 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-16 13:51:06,429 INFO L276 IsEmpty]: Start isEmpty. Operand 99 states and 114 transitions. [2025-03-16 13:51:06,429 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2025-03-16 13:51:06,429 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:51:06,429 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, 1] [2025-03-16 13:51:06,436 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2025-03-16 13:51:06,630 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,SelfDestructingSolverStorable13 [2025-03-16 13:51:06,630 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:51:06,630 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:51:06,630 INFO L85 PathProgramCache]: Analyzing trace with hash -1713726307, now seen corresponding path program 3 times [2025-03-16 13:51:06,630 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:51:06,630 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [906259646] [2025-03-16 13:51:06,630 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 13:51:06,631 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:51:06,635 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 30 statements into 4 equivalence classes. [2025-03-16 13:51:06,659 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) and asserted 30 of 30 statements. [2025-03-16 13:51:06,659 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2025-03-16 13:51:06,659 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 13:51:06,660 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1980919384] [2025-03-16 13:51:06,660 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 13:51:06,660 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:51:06,660 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:51:06,662 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:51:06,663 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2025-03-16 13:51:06,710 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 30 statements into 4 equivalence classes. [2025-03-16 13:51:06,735 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) and asserted 30 of 30 statements. [2025-03-16 13:51:06,735 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2025-03-16 13:51:06,735 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:51:06,736 INFO L256 TraceCheckSpWp]: Trace formula consists of 163 conjuncts, 76 conjuncts are in the unsatisfiable core [2025-03-16 13:51:06,738 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:51:06,760 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 15 treesize of output 1 [2025-03-16 13:51:06,763 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 15 treesize of output 1 [2025-03-16 13:51:06,782 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 23 treesize of output 11 [2025-03-16 13:51:06,789 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 23 treesize of output 11 [2025-03-16 13:51:06,818 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 0 case distinctions, treesize of input 30 treesize of output 21 [2025-03-16 13:51:06,824 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 0 case distinctions, treesize of input 30 treesize of output 21 [2025-03-16 13:51:06,896 INFO L349 Elim1Store]: treesize reduction 54, result has 38.6 percent of original size [2025-03-16 13:51:06,896 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 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 41 treesize of output 43 [2025-03-16 13:51:06,923 INFO L349 Elim1Store]: treesize reduction 54, result has 38.6 percent of original size [2025-03-16 13:51:06,923 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 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 41 treesize of output 43 [2025-03-16 13:51:07,519 INFO L349 Elim1Store]: treesize reduction 238, result has 39.4 percent of original size [2025-03-16 13:51:07,519 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 8 select indices, 8 select index equivalence classes, 3 disjoint index pairs (out of 28 index pairs), introduced 8 new quantified variables, introduced 36 case distinctions, treesize of input 78 treesize of output 188 [2025-03-16 13:51:07,947 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-16 13:51:07,951 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-16 13:51:07,952 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-16 13:51:08,020 INFO L349 Elim1Store]: treesize reduction 190, result has 29.4 percent of original size [2025-03-16 13:51:08,020 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 8 select indices, 8 select index equivalence classes, 6 disjoint index pairs (out of 28 index pairs), introduced 8 new quantified variables, introduced 28 case distinctions, treesize of input 84 treesize of output 131 [2025-03-16 13:51:08,992 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-16 13:51:08,993 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-16 13:51:08,994 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-16 13:51:09,014 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:51:09,014 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 6 select indices, 6 select index equivalence classes, 9 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 15 case distinctions, treesize of input 190 treesize of output 197 [2025-03-16 13:51:09,020 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-16 13:51:09,020 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-16 13:51:09,022 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-16 13:51:09,046 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:51:09,047 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 6 select indices, 6 select index equivalence classes, 9 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 15 case distinctions, treesize of input 154 treesize of output 165 [2025-03-16 13:51:10,319 WARN L672 sPolynomialRelations]: Constructing 64(two to the power of 6 dual juncts. [2025-03-16 13:51:10,335 WARN L672 sPolynomialRelations]: Constructing 64(two to the power of 6 dual juncts. [2025-03-16 13:51:10,770 WARN L672 sPolynomialRelations]: Constructing 64(two to the power of 6 dual juncts. [2025-03-16 13:51:11,203 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 5 proven. 19 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 13:51:11,203 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:51:15,931 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:51:15,931 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [906259646] [2025-03-16 13:51:15,931 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 13:51:15,931 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1980919384] [2025-03-16 13:51:15,931 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1980919384] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:51:15,931 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 13:51:15,931 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2025-03-16 13:51:15,932 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [266850405] [2025-03-16 13:51:15,932 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 13:51:15,932 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2025-03-16 13:51:15,932 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:51:15,932 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-03-16 13:51:15,932 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=129, Invalid=862, Unknown=1, NotChecked=0, Total=992 [2025-03-16 13:51:15,932 INFO L87 Difference]: Start difference. First operand 99 states and 114 transitions. Second operand has 21 states, 21 states have (on average 1.2380952380952381) internal successors, (26), 19 states have internal predecessors, (26), 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-16 13:51:16,718 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:51:16,718 INFO L93 Difference]: Finished difference Result 118 states and 136 transitions. [2025-03-16 13:51:16,719 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2025-03-16 13:51:16,719 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 1.2380952380952381) internal successors, (26), 19 states have internal predecessors, (26), 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 30 [2025-03-16 13:51:16,719 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:51:16,719 INFO L225 Difference]: With dead ends: 118 [2025-03-16 13:51:16,719 INFO L226 Difference]: Without dead ends: 115 [2025-03-16 13:51:16,720 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 12 SyntacticMatches, 0 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 268 ImplicationChecksByTransitivity, 5.7s TimeCoverageRelationStatistics Valid=183, Invalid=1076, Unknown=1, NotChecked=0, Total=1260 [2025-03-16 13:51:16,720 INFO L435 NwaCegarLoop]: 26 mSDtfsCounter, 7 mSDsluCounter, 232 mSDsCounter, 0 mSdLazyCounter, 503 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 258 SdHoareTripleChecker+Invalid, 510 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 503 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2025-03-16 13:51:16,720 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 258 Invalid, 510 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 503 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2025-03-16 13:51:16,721 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 115 states. [2025-03-16 13:51:16,741 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 115 to 103. [2025-03-16 13:51:16,741 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 103 states, 86 states have (on average 1.197674418604651) internal successors, (103), 86 states have internal predecessors, (103), 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-16 13:51:16,741 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 103 states to 103 states and 119 transitions. [2025-03-16 13:51:16,741 INFO L78 Accepts]: Start accepts. Automaton has 103 states and 119 transitions. Word has length 30 [2025-03-16 13:51:16,742 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:51:16,742 INFO L471 AbstractCegarLoop]: Abstraction has 103 states and 119 transitions. [2025-03-16 13:51:16,742 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 1.2380952380952381) internal successors, (26), 19 states have internal predecessors, (26), 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-16 13:51:16,742 INFO L276 IsEmpty]: Start isEmpty. Operand 103 states and 119 transitions. [2025-03-16 13:51:16,742 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2025-03-16 13:51:16,742 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:51:16,742 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, 1] [2025-03-16 13:51:16,748 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-16 13:51:16,942 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:51:16,943 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:51:16,943 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:51:16,943 INFO L85 PathProgramCache]: Analyzing trace with hash -1585876212, now seen corresponding path program 4 times [2025-03-16 13:51:16,943 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:51:16,943 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [55460091] [2025-03-16 13:51:16,943 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 13:51:16,943 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:51:16,949 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 31 statements into 2 equivalence classes. [2025-03-16 13:51:16,966 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 31 of 31 statements. [2025-03-16 13:51:16,966 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-16 13:51:16,966 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:51:17,081 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-16 13:51:17,082 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:51:17,082 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [55460091] [2025-03-16 13:51:17,082 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [55460091] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:51:17,082 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1242306547] [2025-03-16 13:51:17,082 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 13:51:17,082 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:51:17,082 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:51:17,084 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:51:17,086 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2025-03-16 13:51:17,136 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 31 statements into 2 equivalence classes. [2025-03-16 13:51:17,159 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 31 of 31 statements. [2025-03-16 13:51:17,159 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-16 13:51:17,160 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:51:17,160 INFO L256 TraceCheckSpWp]: Trace formula consists of 168 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-03-16 13:51:17,161 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:51:17,228 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-16 13:51:17,228 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:51:17,299 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-16 13:51:17,299 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1242306547] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:51:17,299 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:51:17,299 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13, 13] total 19 [2025-03-16 13:51:17,300 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1514208436] [2025-03-16 13:51:17,300 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:51:17,300 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2025-03-16 13:51:17,300 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:51:17,300 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2025-03-16 13:51:17,300 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=93, Invalid=249, Unknown=0, NotChecked=0, Total=342 [2025-03-16 13:51:17,301 INFO L87 Difference]: Start difference. First operand 103 states and 119 transitions. Second operand has 19 states, 19 states have (on average 1.8421052631578947) internal successors, (35), 19 states have internal predecessors, (35), 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-16 13:51:17,487 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:51:17,487 INFO L93 Difference]: Finished difference Result 146 states and 168 transitions. [2025-03-16 13:51:17,487 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2025-03-16 13:51:17,487 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 1.8421052631578947) internal successors, (35), 19 states have internal predecessors, (35), 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 31 [2025-03-16 13:51:17,487 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:51:17,489 INFO L225 Difference]: With dead ends: 146 [2025-03-16 13:51:17,489 INFO L226 Difference]: Without dead ends: 136 [2025-03-16 13:51:17,489 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 84 GetRequests, 47 SyntacticMatches, 9 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 251 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=242, Invalid=628, Unknown=0, NotChecked=0, Total=870 [2025-03-16 13:51:17,489 INFO L435 NwaCegarLoop]: 21 mSDtfsCounter, 139 mSDsluCounter, 99 mSDsCounter, 0 mSdLazyCounter, 146 mSolverCounterSat, 66 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 140 SdHoareTripleChecker+Valid, 120 SdHoareTripleChecker+Invalid, 212 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 66 IncrementalHoareTripleChecker+Valid, 146 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 13:51:17,489 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [140 Valid, 120 Invalid, 212 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [66 Valid, 146 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 13:51:17,490 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 136 states. [2025-03-16 13:51:17,514 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 136 to 118. [2025-03-16 13:51:17,514 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 118 states, 99 states have (on average 1.202020202020202) internal successors, (119), 99 states have internal predecessors, (119), 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-16 13:51:17,515 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 137 transitions. [2025-03-16 13:51:17,515 INFO L78 Accepts]: Start accepts. Automaton has 118 states and 137 transitions. Word has length 31 [2025-03-16 13:51:17,515 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:51:17,515 INFO L471 AbstractCegarLoop]: Abstraction has 118 states and 137 transitions. [2025-03-16 13:51:17,515 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 1.8421052631578947) internal successors, (35), 19 states have internal predecessors, (35), 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-16 13:51:17,515 INFO L276 IsEmpty]: Start isEmpty. Operand 118 states and 137 transitions. [2025-03-16 13:51:17,515 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2025-03-16 13:51:17,515 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:51:17,516 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, 1] [2025-03-16 13:51:17,521 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2025-03-16 13:51:17,716 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,SelfDestructingSolverStorable15 [2025-03-16 13:51:17,716 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:51:17,716 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:51:17,716 INFO L85 PathProgramCache]: Analyzing trace with hash 217996755, now seen corresponding path program 10 times [2025-03-16 13:51:17,717 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:51:17,717 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1291279716] [2025-03-16 13:51:17,717 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 13:51:17,717 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:51:17,721 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 31 statements into 2 equivalence classes. [2025-03-16 13:51:17,729 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 31 of 31 statements. [2025-03-16 13:51:17,730 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-16 13:51:17,730 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:51:17,839 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-16 13:51:17,840 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:51:17,840 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1291279716] [2025-03-16 13:51:17,840 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1291279716] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:51:17,840 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1203951944] [2025-03-16 13:51:17,840 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 13:51:17,840 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:51:17,840 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:51:17,845 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:51:17,846 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2025-03-16 13:51:17,896 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 31 statements into 2 equivalence classes. [2025-03-16 13:51:17,960 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 31 of 31 statements. [2025-03-16 13:51:17,960 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-16 13:51:17,960 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:51:17,961 INFO L256 TraceCheckSpWp]: Trace formula consists of 177 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-03-16 13:51:17,962 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:51:18,031 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-16 13:51:18,032 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:51:18,093 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-16 13:51:18,093 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1203951944] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:51:18,093 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:51:18,093 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13, 13] total 19 [2025-03-16 13:51:18,094 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1641945318] [2025-03-16 13:51:18,094 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:51:18,094 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2025-03-16 13:51:18,094 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:51:18,094 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2025-03-16 13:51:18,094 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=97, Invalid=245, Unknown=0, NotChecked=0, Total=342 [2025-03-16 13:51:18,094 INFO L87 Difference]: Start difference. First operand 118 states and 137 transitions. Second operand has 19 states, 19 states have (on average 1.8421052631578947) internal successors, (35), 19 states have internal predecessors, (35), 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-16 13:51:18,239 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:51:18,239 INFO L93 Difference]: Finished difference Result 137 states and 156 transitions. [2025-03-16 13:51:18,239 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2025-03-16 13:51:18,240 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 1.8421052631578947) internal successors, (35), 19 states have internal predecessors, (35), 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 31 [2025-03-16 13:51:18,240 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:51:18,240 INFO L225 Difference]: With dead ends: 137 [2025-03-16 13:51:18,240 INFO L226 Difference]: Without dead ends: 134 [2025-03-16 13:51:18,241 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 78 GetRequests, 46 SyntacticMatches, 10 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 216 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=152, Invalid=400, Unknown=0, NotChecked=0, Total=552 [2025-03-16 13:51:18,241 INFO L435 NwaCegarLoop]: 25 mSDtfsCounter, 42 mSDsluCounter, 105 mSDsCounter, 0 mSdLazyCounter, 158 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 43 SdHoareTripleChecker+Valid, 130 SdHoareTripleChecker+Invalid, 187 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 158 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 13:51:18,241 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [43 Valid, 130 Invalid, 187 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 158 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 13:51:18,241 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 134 states. [2025-03-16 13:51:18,265 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 134 to 104. [2025-03-16 13:51:18,265 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 104 states, 87 states have (on average 1.1954022988505748) internal successors, (104), 87 states have internal predecessors, (104), 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-16 13:51:18,265 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 104 states to 104 states and 120 transitions. [2025-03-16 13:51:18,265 INFO L78 Accepts]: Start accepts. Automaton has 104 states and 120 transitions. Word has length 31 [2025-03-16 13:51:18,266 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:51:18,266 INFO L471 AbstractCegarLoop]: Abstraction has 104 states and 120 transitions. [2025-03-16 13:51:18,266 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 1.8421052631578947) internal successors, (35), 19 states have internal predecessors, (35), 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-16 13:51:18,266 INFO L276 IsEmpty]: Start isEmpty. Operand 104 states and 120 transitions. [2025-03-16 13:51:18,266 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2025-03-16 13:51:18,266 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:51:18,266 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, 1] [2025-03-16 13:51:18,273 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Ended with exit code 0 [2025-03-16 13:51:18,470 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2025-03-16 13:51:18,470 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:51:18,470 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:51:18,470 INFO L85 PathProgramCache]: Analyzing trace with hash -1832003434, now seen corresponding path program 11 times [2025-03-16 13:51:18,470 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:51:18,470 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1316539158] [2025-03-16 13:51:18,470 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-16 13:51:18,470 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:51:18,475 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 32 statements into 5 equivalence classes. [2025-03-16 13:51:18,500 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 5 check-sat command(s) and asserted 32 of 32 statements. [2025-03-16 13:51:18,501 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 5 check-sat command(s) [2025-03-16 13:51:18,501 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 13:51:18,501 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1125546128] [2025-03-16 13:51:18,501 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-16 13:51:18,501 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:51:18,502 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:51:18,503 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:51:18,508 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2025-03-16 13:51:18,559 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 32 statements into 5 equivalence classes. [2025-03-16 13:51:18,612 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 5 check-sat command(s) and asserted 32 of 32 statements. [2025-03-16 13:51:18,612 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 5 check-sat command(s) [2025-03-16 13:51:18,612 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:51:18,615 INFO L256 TraceCheckSpWp]: Trace formula consists of 182 conjuncts, 79 conjuncts are in the unsatisfiable core [2025-03-16 13:51:18,618 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:51:18,639 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 15 treesize of output 1 [2025-03-16 13:51:18,649 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 15 treesize of output 1 [2025-03-16 13:51:18,671 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 23 treesize of output 11 [2025-03-16 13:51:18,677 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 23 treesize of output 11 [2025-03-16 13:51:18,713 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 0 case distinctions, treesize of input 30 treesize of output 21 [2025-03-16 13:51:18,721 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 0 case distinctions, treesize of input 30 treesize of output 21 [2025-03-16 13:51:18,769 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 0 case distinctions, treesize of input 37 treesize of output 31 [2025-03-16 13:51:18,780 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 0 case distinctions, treesize of input 37 treesize of output 31 [2025-03-16 13:51:18,827 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 0 case distinctions, treesize of input 44 treesize of output 41 [2025-03-16 13:51:18,840 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 0 case distinctions, treesize of input 44 treesize of output 41 [2025-03-16 13:51:19,364 INFO L349 Elim1Store]: treesize reduction 160, result has 48.6 percent of original size [2025-03-16 13:51:19,365 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 10 select indices, 10 select index equivalence classes, 10 disjoint index pairs (out of 45 index pairs), introduced 10 new quantified variables, introduced 55 case distinctions, treesize of input 84 treesize of output 190 [2025-03-16 13:51:20,371 INFO L349 Elim1Store]: treesize reduction 256, result has 45.6 percent of original size [2025-03-16 13:51:20,371 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 105 treesize of output 254 [2025-03-16 13:51:34,061 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:51:34,061 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 21 select indices, 21 select index equivalence classes, 10 disjoint index pairs (out of 210 index pairs), introduced 21 new quantified variables, introduced 210 case distinctions, treesize of input 1757 treesize of output 2909 [2025-03-16 13:51:44,697 WARN L286 SmtUtils]: Spent 10.39s on a formula simplification. DAG size of input: 1164 DAG size of output: 684 (called from [L 346] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.arrays.Elim1Store.elim1) [2025-03-16 13:51:44,697 INFO L349 Elim1Store]: treesize reduction 2880, result has 32.9 percent of original size [2025-03-16 13:51:44,698 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 37 select indices, 37 select index equivalence classes, 10 disjoint index pairs (out of 666 index pairs), introduced 37 new quantified variables, introduced 666 case distinctions, treesize of input 1309 treesize of output 2209 [2025-03-16 13:51:57,515 WARN L672 sPolynomialRelations]: Constructing 4096(two to the power of 12 dual juncts.