./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench/egcd3-ll.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version c7c6ca5d Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/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.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench/egcd3-ll.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 4ef08007570a64191e0df13d14d3e8d62a8022f43f46779ea6f6701a621376be --- Real Ultimate output --- This is Ultimate 0.2.5-?-c7c6ca5-m [2024-11-08 14:16:06,430 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-08 14:16:06,469 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-08 14:16:06,472 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-08 14:16:06,472 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-08 14:16:06,494 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-08 14:16:06,497 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-08 14:16:06,500 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-08 14:16:06,501 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-08 14:16:06,501 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-08 14:16:06,501 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-08 14:16:06,502 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-08 14:16:06,502 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-08 14:16:06,502 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-08 14:16:06,503 INFO L153 SettingsManager]: * Use SBE=true [2024-11-08 14:16:06,503 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-08 14:16:06,503 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-08 14:16:06,503 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-08 14:16:06,504 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-08 14:16:06,504 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-08 14:16:06,505 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-08 14:16:06,505 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-08 14:16:06,506 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-08 14:16:06,506 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-08 14:16:06,506 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-08 14:16:06,507 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-08 14:16:06,507 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-08 14:16:06,507 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-08 14:16:06,508 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-08 14:16:06,508 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-08 14:16:06,508 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-08 14:16:06,508 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-08 14:16:06,509 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-08 14:16:06,509 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-08 14:16:06,513 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-08 14:16:06,513 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-08 14:16:06,514 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-08 14:16:06,514 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-08 14:16:06,514 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-08 14:16:06,514 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-08 14:16:06,514 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-08 14:16:06,515 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-08 14:16:06,515 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 4ef08007570a64191e0df13d14d3e8d62a8022f43f46779ea6f6701a621376be [2024-11-08 14:16:06,737 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-08 14:16:06,773 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-08 14:16:06,775 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-08 14:16:06,776 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-08 14:16:06,776 INFO L274 PluginConnector]: CDTParser initialized [2024-11-08 14:16:06,777 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench/egcd3-ll.c [2024-11-08 14:16:08,016 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-08 14:16:08,132 INFO L384 CDTParser]: Found 1 translation units. [2024-11-08 14:16:08,133 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench/egcd3-ll.c [2024-11-08 14:16:08,138 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/87c64ebb2/3eb910918525447fa236ddf1dcea2ce2/FLAG51a2d38cf [2024-11-08 14:16:08,148 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/87c64ebb2/3eb910918525447fa236ddf1dcea2ce2 [2024-11-08 14:16:08,149 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-08 14:16:08,150 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-08 14:16:08,151 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-08 14:16:08,151 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-08 14:16:08,155 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-08 14:16:08,155 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.11 02:16:08" (1/1) ... [2024-11-08 14:16:08,156 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@20f38ef5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:16:08, skipping insertion in model container [2024-11-08 14:16:08,156 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.11 02:16:08" (1/1) ... [2024-11-08 14:16:08,169 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-08 14:16:08,306 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench/egcd3-ll.c[490,503] [2024-11-08 14:16:08,322 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-08 14:16:08,332 INFO L200 MainTranslator]: Completed pre-run [2024-11-08 14:16:08,341 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench/egcd3-ll.c[490,503] [2024-11-08 14:16:08,351 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-08 14:16:08,364 INFO L204 MainTranslator]: Completed translation [2024-11-08 14:16:08,364 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:16:08 WrapperNode [2024-11-08 14:16:08,364 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-08 14:16:08,365 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-08 14:16:08,365 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-08 14:16:08,365 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-08 14:16:08,371 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:16:08" (1/1) ... [2024-11-08 14:16:08,378 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:16:08" (1/1) ... [2024-11-08 14:16:08,405 INFO L138 Inliner]: procedures = 14, calls = 14, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 81 [2024-11-08 14:16:08,411 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-08 14:16:08,413 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-08 14:16:08,413 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-08 14:16:08,414 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-08 14:16:08,426 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:16:08" (1/1) ... [2024-11-08 14:16:08,426 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:16:08" (1/1) ... [2024-11-08 14:16:08,428 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:16:08" (1/1) ... [2024-11-08 14:16:08,443 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-11-08 14:16:08,448 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:16:08" (1/1) ... [2024-11-08 14:16:08,448 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:16:08" (1/1) ... [2024-11-08 14:16:08,451 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:16:08" (1/1) ... [2024-11-08 14:16:08,459 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:16:08" (1/1) ... [2024-11-08 14:16:08,466 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:16:08" (1/1) ... [2024-11-08 14:16:08,466 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:16:08" (1/1) ... [2024-11-08 14:16:08,472 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-08 14:16:08,472 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-08 14:16:08,472 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-08 14:16:08,472 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-08 14:16:08,473 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:16:08" (1/1) ... [2024-11-08 14:16:08,484 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-08 14:16:08,492 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:16:08,512 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) [2024-11-08 14:16:08,514 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 [2024-11-08 14:16:08,550 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-08 14:16:08,551 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-08 14:16:08,551 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-08 14:16:08,551 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-08 14:16:08,551 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-08 14:16:08,551 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-08 14:16:08,551 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-08 14:16:08,551 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-08 14:16:08,600 INFO L238 CfgBuilder]: Building ICFG [2024-11-08 14:16:08,601 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-08 14:16:08,718 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-11-08 14:16:08,719 INFO L287 CfgBuilder]: Performing block encoding [2024-11-08 14:16:08,727 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-08 14:16:08,728 INFO L316 CfgBuilder]: Removed 3 assume(true) statements. [2024-11-08 14:16:08,728 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.11 02:16:08 BoogieIcfgContainer [2024-11-08 14:16:08,728 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-08 14:16:08,730 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-08 14:16:08,730 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-08 14:16:08,733 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-08 14:16:08,733 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 08.11 02:16:08" (1/3) ... [2024-11-08 14:16:08,734 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3b2f3240 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.11 02:16:08, skipping insertion in model container [2024-11-08 14:16:08,734 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:16:08" (2/3) ... [2024-11-08 14:16:08,734 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3b2f3240 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.11 02:16:08, skipping insertion in model container [2024-11-08 14:16:08,734 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.11 02:16:08" (3/3) ... [2024-11-08 14:16:08,735 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd3-ll.c [2024-11-08 14:16:08,748 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-08 14:16:08,748 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-08 14:16:08,787 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-08 14:16:08,792 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;@4c19dac5, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-08 14:16:08,792 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-08 14:16:08,795 INFO L276 IsEmpty]: Start isEmpty. Operand has 32 states, 21 states have (on average 1.5714285714285714) internal successors, (33), 22 states have internal predecessors, (33), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-08 14:16:08,801 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2024-11-08 14:16:08,801 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:08,801 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:08,802 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:08,806 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:08,806 INFO L85 PathProgramCache]: Analyzing trace with hash -149497031, now seen corresponding path program 1 times [2024-11-08 14:16:08,820 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:08,823 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2100214488] [2024-11-08 14:16:08,823 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:08,824 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:08,890 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:08,928 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 14:16:08,930 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:08,940 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-08 14:16:08,942 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:08,947 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-08 14:16:08,948 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:08,948 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2100214488] [2024-11-08 14:16:08,950 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2100214488] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:16:08,950 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:16:08,950 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-08 14:16:08,951 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [553320345] [2024-11-08 14:16:08,951 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:16:08,955 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-08 14:16:08,955 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:08,973 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-08 14:16:08,974 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-08 14:16:08,975 INFO L87 Difference]: Start difference. First operand has 32 states, 21 states have (on average 1.5714285714285714) internal successors, (33), 22 states have internal predecessors, (33), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-08 14:16:08,989 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:08,990 INFO L93 Difference]: Finished difference Result 61 states and 97 transitions. [2024-11-08 14:16:08,991 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-08 14:16:08,991 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 18 [2024-11-08 14:16:08,992 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:08,996 INFO L225 Difference]: With dead ends: 61 [2024-11-08 14:16:08,996 INFO L226 Difference]: Without dead ends: 28 [2024-11-08 14:16:08,999 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-08 14:16:09,001 INFO L432 NwaCegarLoop]: 39 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, 39 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 [2024-11-08 14:16:09,002 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:16:09,038 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2024-11-08 14:16:09,088 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 28. [2024-11-08 14:16:09,089 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 18 states have (on average 1.2222222222222223) internal successors, (22), 19 states have internal predecessors, (22), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-08 14:16:09,095 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 35 transitions. [2024-11-08 14:16:09,097 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 35 transitions. Word has length 18 [2024-11-08 14:16:09,097 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:09,097 INFO L471 AbstractCegarLoop]: Abstraction has 28 states and 35 transitions. [2024-11-08 14:16:09,099 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-08 14:16:09,100 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 35 transitions. [2024-11-08 14:16:09,101 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2024-11-08 14:16:09,101 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:09,101 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:09,102 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-08 14:16:09,102 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:09,102 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:09,103 INFO L85 PathProgramCache]: Analyzing trace with hash -2030119444, now seen corresponding path program 1 times [2024-11-08 14:16:09,103 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:09,103 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1969961879] [2024-11-08 14:16:09,103 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:09,103 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:09,146 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:09,281 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 14:16:09,283 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:09,287 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-08 14:16:09,289 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:09,325 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-08 14:16:09,325 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:09,325 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1969961879] [2024-11-08 14:16:09,326 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1969961879] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:16:09,326 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:16:09,326 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-08 14:16:09,326 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [55989902] [2024-11-08 14:16:09,326 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:16:09,327 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-08 14:16:09,327 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:09,327 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-08 14:16:09,327 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-08 14:16:09,328 INFO L87 Difference]: Start difference. First operand 28 states and 35 transitions. Second operand has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-08 14:16:09,479 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:09,479 INFO L93 Difference]: Finished difference Result 47 states and 60 transitions. [2024-11-08 14:16:09,480 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-08 14:16:09,480 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 19 [2024-11-08 14:16:09,481 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:09,481 INFO L225 Difference]: With dead ends: 47 [2024-11-08 14:16:09,481 INFO L226 Difference]: Without dead ends: 40 [2024-11-08 14:16:09,482 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-08 14:16:09,482 INFO L432 NwaCegarLoop]: 27 mSDtfsCounter, 28 mSDsluCounter, 68 mSDsCounter, 0 mSdLazyCounter, 41 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 36 SdHoareTripleChecker+Valid, 95 SdHoareTripleChecker+Invalid, 45 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 41 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:09,483 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [36 Valid, 95 Invalid, 45 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 14:16:09,483 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2024-11-08 14:16:09,498 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 30. [2024-11-08 14:16:09,499 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 20 states have (on average 1.2) internal successors, (24), 21 states have internal predecessors, (24), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-08 14:16:09,499 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 37 transitions. [2024-11-08 14:16:09,500 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 37 transitions. Word has length 19 [2024-11-08 14:16:09,500 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:09,500 INFO L471 AbstractCegarLoop]: Abstraction has 30 states and 37 transitions. [2024-11-08 14:16:09,500 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-08 14:16:09,500 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 37 transitions. [2024-11-08 14:16:09,500 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2024-11-08 14:16:09,501 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:09,501 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:09,501 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-08 14:16:09,501 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:09,506 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:09,506 INFO L85 PathProgramCache]: Analyzing trace with hash 1778657237, now seen corresponding path program 1 times [2024-11-08 14:16:09,506 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:09,506 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2035881769] [2024-11-08 14:16:09,506 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:09,507 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:09,544 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:16:09,545 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1888279586] [2024-11-08 14:16:09,545 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:09,546 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:09,546 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:16:09,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) [2024-11-08 14:16:09,554 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-08 14:16:09,606 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:09,611 INFO L255 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-08 14:16:09,615 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:16:09,738 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-08 14:16:09,739 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-08 14:16:09,739 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:09,739 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2035881769] [2024-11-08 14:16:09,740 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:16:09,740 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1888279586] [2024-11-08 14:16:09,741 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1888279586] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:16:09,741 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:16:09,742 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-08 14:16:09,742 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1026273162] [2024-11-08 14:16:09,742 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:16:09,742 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:16:09,742 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:09,743 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:16:09,743 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-08 14:16:09,743 INFO L87 Difference]: Start difference. First operand 30 states and 37 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-08 14:16:09,790 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:09,790 INFO L93 Difference]: Finished difference Result 46 states and 58 transitions. [2024-11-08 14:16:09,791 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 14:16:09,791 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 22 [2024-11-08 14:16:09,791 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:09,794 INFO L225 Difference]: With dead ends: 46 [2024-11-08 14:16:09,795 INFO L226 Difference]: Without dead ends: 44 [2024-11-08 14:16:09,795 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-08 14:16:09,796 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 7 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 114 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:09,798 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 114 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:16:09,798 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2024-11-08 14:16:09,807 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 43. [2024-11-08 14:16:09,809 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 28 states have (on average 1.2142857142857142) internal successors, (34), 29 states have internal predecessors, (34), 11 states have call successors, (11), 3 states have call predecessors, (11), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-08 14:16:09,811 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 55 transitions. [2024-11-08 14:16:09,811 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 55 transitions. Word has length 22 [2024-11-08 14:16:09,811 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:09,812 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 55 transitions. [2024-11-08 14:16:09,812 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-08 14:16:09,812 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 55 transitions. [2024-11-08 14:16:09,813 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2024-11-08 14:16:09,814 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:09,814 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:09,831 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-08 14:16:10,018 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:10,019 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:10,020 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:10,020 INFO L85 PathProgramCache]: Analyzing trace with hash 646289443, now seen corresponding path program 1 times [2024-11-08 14:16:10,020 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:10,020 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [754142926] [2024-11-08 14:16:10,020 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:10,020 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:10,042 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:10,130 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 14:16:10,132 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:10,158 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-08 14:16:10,160 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:10,162 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-08 14:16:10,162 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:10,162 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [754142926] [2024-11-08 14:16:10,163 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [754142926] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:16:10,163 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1411369520] [2024-11-08 14:16:10,163 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:10,163 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:10,163 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:16:10,164 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) [2024-11-08 14:16:10,170 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-08 14:16:10,214 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:10,215 INFO L255 TraceCheckSpWp]: Trace formula consists of 87 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-08 14:16:10,216 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:16:10,251 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-08 14:16:10,253 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:16:10,319 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-08 14:16:10,319 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1411369520] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:16:10,319 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 14:16:10,319 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 9 [2024-11-08 14:16:10,319 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [709688091] [2024-11-08 14:16:10,319 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 14:16:10,320 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-08 14:16:10,320 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:10,320 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-08 14:16:10,320 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2024-11-08 14:16:10,321 INFO L87 Difference]: Start difference. First operand 43 states and 55 transitions. Second operand has 9 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 8 states have internal predecessors, (21), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-08 14:16:10,555 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:10,557 INFO L93 Difference]: Finished difference Result 96 states and 134 transitions. [2024-11-08 14:16:10,557 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-08 14:16:10,557 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 8 states have internal predecessors, (21), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 24 [2024-11-08 14:16:10,558 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:10,559 INFO L225 Difference]: With dead ends: 96 [2024-11-08 14:16:10,559 INFO L226 Difference]: Without dead ends: 89 [2024-11-08 14:16:10,560 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 61 GetRequests, 46 SyntacticMatches, 4 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=42, Invalid=114, Unknown=0, NotChecked=0, Total=156 [2024-11-08 14:16:10,561 INFO L432 NwaCegarLoop]: 37 mSDtfsCounter, 57 mSDsluCounter, 213 mSDsCounter, 0 mSdLazyCounter, 112 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 61 SdHoareTripleChecker+Valid, 250 SdHoareTripleChecker+Invalid, 138 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 112 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:10,563 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [61 Valid, 250 Invalid, 138 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 112 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 14:16:10,563 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states. [2024-11-08 14:16:10,582 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 64. [2024-11-08 14:16:10,585 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 45 states have (on average 1.2666666666666666) internal successors, (57), 46 states have internal predecessors, (57), 15 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2024-11-08 14:16:10,586 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 86 transitions. [2024-11-08 14:16:10,586 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 86 transitions. Word has length 24 [2024-11-08 14:16:10,586 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:10,586 INFO L471 AbstractCegarLoop]: Abstraction has 64 states and 86 transitions. [2024-11-08 14:16:10,586 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 8 states have internal predecessors, (21), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-08 14:16:10,588 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 86 transitions. [2024-11-08 14:16:10,589 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2024-11-08 14:16:10,589 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:10,589 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:10,602 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-08 14:16:10,789 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,SelfDestructingSolverStorable3 [2024-11-08 14:16:10,790 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:10,790 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:10,791 INFO L85 PathProgramCache]: Analyzing trace with hash 1194834104, now seen corresponding path program 1 times [2024-11-08 14:16:10,791 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:10,794 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1838960121] [2024-11-08 14:16:10,794 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:10,794 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:10,818 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:16:10,819 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1872759144] [2024-11-08 14:16:10,819 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:10,819 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:10,820 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:16:10,826 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) [2024-11-08 14:16:10,828 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-08 14:16:10,875 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:10,876 INFO L255 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-08 14:16:10,877 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:16:11,028 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-08 14:16:11,028 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-08 14:16:11,028 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:11,028 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1838960121] [2024-11-08 14:16:11,028 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:16:11,029 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1872759144] [2024-11-08 14:16:11,029 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1872759144] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:16:11,029 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:16:11,029 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-08 14:16:11,030 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1290724051] [2024-11-08 14:16:11,030 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:16:11,031 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:16:11,031 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:11,032 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:16:11,033 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-08 14:16:11,033 INFO L87 Difference]: Start difference. First operand 64 states and 86 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-08 14:16:11,080 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:11,081 INFO L93 Difference]: Finished difference Result 72 states and 93 transitions. [2024-11-08 14:16:11,081 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 14:16:11,084 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 27 [2024-11-08 14:16:11,084 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:11,085 INFO L225 Difference]: With dead ends: 72 [2024-11-08 14:16:11,085 INFO L226 Difference]: Without dead ends: 70 [2024-11-08 14:16:11,085 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 27 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-08 14:16:11,086 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 7 mSDsluCounter, 81 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 112 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:11,086 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 112 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:16:11,087 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 70 states. [2024-11-08 14:16:11,103 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 70 to 68. [2024-11-08 14:16:11,105 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 68 states, 48 states have (on average 1.25) internal successors, (60), 49 states have internal predecessors, (60), 15 states have call successors, (15), 4 states have call predecessors, (15), 4 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2024-11-08 14:16:11,106 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 68 states to 68 states and 89 transitions. [2024-11-08 14:16:11,108 INFO L78 Accepts]: Start accepts. Automaton has 68 states and 89 transitions. Word has length 27 [2024-11-08 14:16:11,109 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:11,109 INFO L471 AbstractCegarLoop]: Abstraction has 68 states and 89 transitions. [2024-11-08 14:16:11,109 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-08 14:16:11,109 INFO L276 IsEmpty]: Start isEmpty. Operand 68 states and 89 transitions. [2024-11-08 14:16:11,109 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2024-11-08 14:16:11,109 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:11,110 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:11,133 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-08 14:16:11,310 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:11,310 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:11,311 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:11,315 INFO L85 PathProgramCache]: Analyzing trace with hash -1392040386, now seen corresponding path program 1 times [2024-11-08 14:16:11,315 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:11,315 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [436818156] [2024-11-08 14:16:11,315 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:11,316 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:11,332 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:16:11,332 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1671232363] [2024-11-08 14:16:11,333 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:11,333 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:11,333 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:16:11,338 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) [2024-11-08 14:16:11,340 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-08 14:16:11,384 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:11,385 INFO L255 TraceCheckSpWp]: Trace formula consists of 97 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-11-08 14:16:11,386 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:16:11,471 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-08 14:16:11,471 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:16:11,576 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-08 14:16:11,580 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:11,580 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [436818156] [2024-11-08 14:16:11,580 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:16:11,580 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1671232363] [2024-11-08 14:16:11,580 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1671232363] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:16:11,581 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 14:16:11,581 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2024-11-08 14:16:11,581 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [366663016] [2024-11-08 14:16:11,581 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 14:16:11,581 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-08 14:16:11,581 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:11,582 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-08 14:16:11,582 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-08 14:16:11,582 INFO L87 Difference]: Start difference. First operand 68 states and 89 transitions. Second operand has 8 states, 8 states have (on average 3.75) internal successors, (30), 7 states have internal predecessors, (30), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-08 14:16:11,854 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:11,854 INFO L93 Difference]: Finished difference Result 104 states and 138 transitions. [2024-11-08 14:16:11,854 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-08 14:16:11,855 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.75) internal successors, (30), 7 states have internal predecessors, (30), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 27 [2024-11-08 14:16:11,855 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:11,856 INFO L225 Difference]: With dead ends: 104 [2024-11-08 14:16:11,856 INFO L226 Difference]: Without dead ends: 102 [2024-11-08 14:16:11,856 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 53 GetRequests, 44 SyntacticMatches, 2 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2024-11-08 14:16:11,857 INFO L432 NwaCegarLoop]: 46 mSDtfsCounter, 18 mSDsluCounter, 166 mSDsCounter, 0 mSdLazyCounter, 76 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 212 SdHoareTripleChecker+Invalid, 81 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 76 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:11,857 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [26 Valid, 212 Invalid, 81 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 76 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-08 14:16:11,857 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 102 states. [2024-11-08 14:16:11,867 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 102 to 98. [2024-11-08 14:16:11,867 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 98 states, 69 states have (on average 1.2608695652173914) internal successors, (87), 70 states have internal predecessors, (87), 23 states have call successors, (23), 5 states have call predecessors, (23), 5 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2024-11-08 14:16:11,868 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 132 transitions. [2024-11-08 14:16:11,868 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 132 transitions. Word has length 27 [2024-11-08 14:16:11,868 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:11,869 INFO L471 AbstractCegarLoop]: Abstraction has 98 states and 132 transitions. [2024-11-08 14:16:11,869 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.75) internal successors, (30), 7 states have internal predecessors, (30), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-08 14:16:11,869 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 132 transitions. [2024-11-08 14:16:11,869 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2024-11-08 14:16:11,870 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:11,870 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:11,882 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-08 14:16:12,073 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:12,074 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:12,074 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:12,074 INFO L85 PathProgramCache]: Analyzing trace with hash -281586315, now seen corresponding path program 1 times [2024-11-08 14:16:12,075 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:12,075 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1701900477] [2024-11-08 14:16:12,075 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:12,075 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:12,084 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:16:12,084 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1549557962] [2024-11-08 14:16:12,084 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:12,085 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:12,085 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:16:12,089 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) [2024-11-08 14:16:12,094 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-08 14:16:12,127 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:12,128 INFO L255 TraceCheckSpWp]: Trace formula consists of 95 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-08 14:16:12,129 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:16:12,193 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-11-08 14:16:12,194 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-08 14:16:12,194 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:12,194 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1701900477] [2024-11-08 14:16:12,194 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:16:12,194 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1549557962] [2024-11-08 14:16:12,195 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1549557962] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:16:12,195 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:16:12,195 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-08 14:16:12,195 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [696386775] [2024-11-08 14:16:12,195 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:16:12,195 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:16:12,195 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:12,196 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:16:12,197 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-08 14:16:12,197 INFO L87 Difference]: Start difference. First operand 98 states and 132 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-08 14:16:12,276 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:12,276 INFO L93 Difference]: Finished difference Result 144 states and 204 transitions. [2024-11-08 14:16:12,276 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 14:16:12,277 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 32 [2024-11-08 14:16:12,278 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:12,279 INFO L225 Difference]: With dead ends: 144 [2024-11-08 14:16:12,279 INFO L226 Difference]: Without dead ends: 142 [2024-11-08 14:16:12,280 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-08 14:16:12,282 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 6 mSDsluCounter, 75 mSDsCounter, 0 mSdLazyCounter, 43 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 104 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 43 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:12,282 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 104 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 43 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 14:16:12,283 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 142 states. [2024-11-08 14:16:12,308 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 142 to 136. [2024-11-08 14:16:12,309 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 136 states, 86 states have (on average 1.2906976744186047) internal successors, (111), 87 states have internal predecessors, (111), 43 states have call successors, (43), 6 states have call predecessors, (43), 6 states have return successors, (42), 42 states have call predecessors, (42), 42 states have call successors, (42) [2024-11-08 14:16:12,311 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 136 states to 136 states and 196 transitions. [2024-11-08 14:16:12,312 INFO L78 Accepts]: Start accepts. Automaton has 136 states and 196 transitions. Word has length 32 [2024-11-08 14:16:12,312 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:12,312 INFO L471 AbstractCegarLoop]: Abstraction has 136 states and 196 transitions. [2024-11-08 14:16:12,312 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-08 14:16:12,312 INFO L276 IsEmpty]: Start isEmpty. Operand 136 states and 196 transitions. [2024-11-08 14:16:12,313 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2024-11-08 14:16:12,315 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:12,315 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:12,328 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-08 14:16:12,518 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:12,519 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:12,519 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:12,520 INFO L85 PathProgramCache]: Analyzing trace with hash -1215278097, now seen corresponding path program 1 times [2024-11-08 14:16:12,520 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:12,520 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [624745592] [2024-11-08 14:16:12,520 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:12,520 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:12,530 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:16:12,531 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1867001173] [2024-11-08 14:16:12,531 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:12,531 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:12,531 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:16:12,532 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) [2024-11-08 14:16:12,533 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-08 14:16:12,566 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:12,567 INFO L255 TraceCheckSpWp]: Trace formula consists of 106 conjuncts, 21 conjuncts are in the unsatisfiable core [2024-11-08 14:16:12,568 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:16:12,677 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 2 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-08 14:16:12,677 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:16:12,711 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:12,711 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [624745592] [2024-11-08 14:16:12,711 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:16:12,711 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1867001173] [2024-11-08 14:16:12,711 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1867001173] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:16:12,711 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-08 14:16:12,711 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2024-11-08 14:16:12,712 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [525531186] [2024-11-08 14:16:12,712 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-08 14:16:12,712 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-08 14:16:12,712 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:12,712 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-08 14:16:12,713 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2024-11-08 14:16:12,713 INFO L87 Difference]: Start difference. First operand 136 states and 196 transitions. Second operand has 7 states, 7 states have (on average 3.142857142857143) internal successors, (22), 6 states have internal predecessors, (22), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-08 14:16:12,890 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:12,890 INFO L93 Difference]: Finished difference Result 149 states and 207 transitions. [2024-11-08 14:16:12,894 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-08 14:16:12,894 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.142857142857143) internal successors, (22), 6 states have internal predecessors, (22), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 32 [2024-11-08 14:16:12,895 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:12,896 INFO L225 Difference]: With dead ends: 149 [2024-11-08 14:16:12,896 INFO L226 Difference]: Without dead ends: 147 [2024-11-08 14:16:12,896 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 38 GetRequests, 28 SyntacticMatches, 2 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2024-11-08 14:16:12,897 INFO L432 NwaCegarLoop]: 37 mSDtfsCounter, 26 mSDsluCounter, 142 mSDsCounter, 0 mSdLazyCounter, 109 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 179 SdHoareTripleChecker+Invalid, 120 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 109 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:12,897 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [33 Valid, 179 Invalid, 120 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 109 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 14:16:12,898 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 147 states. [2024-11-08 14:16:12,921 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 147 to 144. [2024-11-08 14:16:12,921 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 144 states, 92 states have (on average 1.2717391304347827) internal successors, (117), 93 states have internal predecessors, (117), 43 states have call successors, (43), 8 states have call predecessors, (43), 8 states have return successors, (42), 42 states have call predecessors, (42), 42 states have call successors, (42) [2024-11-08 14:16:12,922 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 144 states to 144 states and 202 transitions. [2024-11-08 14:16:12,922 INFO L78 Accepts]: Start accepts. Automaton has 144 states and 202 transitions. Word has length 32 [2024-11-08 14:16:12,922 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:12,922 INFO L471 AbstractCegarLoop]: Abstraction has 144 states and 202 transitions. [2024-11-08 14:16:12,923 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 3.142857142857143) internal successors, (22), 6 states have internal predecessors, (22), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-08 14:16:12,923 INFO L276 IsEmpty]: Start isEmpty. Operand 144 states and 202 transitions. [2024-11-08 14:16:12,923 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2024-11-08 14:16:12,923 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:12,923 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:12,937 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-08 14:16:13,127 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:13,128 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:13,128 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:13,128 INFO L85 PathProgramCache]: Analyzing trace with hash 492814709, now seen corresponding path program 2 times [2024-11-08 14:16:13,128 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:13,128 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1039109921] [2024-11-08 14:16:13,128 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:13,128 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:13,136 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:13,178 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 14:16:13,179 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:13,180 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-08 14:16:13,180 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:13,182 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 13 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-08 14:16:13,182 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:13,182 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1039109921] [2024-11-08 14:16:13,182 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1039109921] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:16:13,182 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:16:13,182 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-08 14:16:13,182 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1393844639] [2024-11-08 14:16:13,182 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:16:13,183 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:16:13,183 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:13,183 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:16:13,183 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-08 14:16:13,183 INFO L87 Difference]: Start difference. First operand 144 states and 202 transitions. Second operand has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-08 14:16:13,249 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:13,249 INFO L93 Difference]: Finished difference Result 183 states and 254 transitions. [2024-11-08 14:16:13,249 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-08 14:16:13,249 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 32 [2024-11-08 14:16:13,250 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:13,250 INFO L225 Difference]: With dead ends: 183 [2024-11-08 14:16:13,251 INFO L226 Difference]: Without dead ends: 127 [2024-11-08 14:16:13,251 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2024-11-08 14:16:13,252 INFO L432 NwaCegarLoop]: 44 mSDtfsCounter, 18 mSDsluCounter, 96 mSDsCounter, 0 mSdLazyCounter, 54 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 140 SdHoareTripleChecker+Invalid, 62 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 54 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:13,252 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 140 Invalid, 62 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 54 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:16:13,252 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 127 states. [2024-11-08 14:16:13,263 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 127 to 119. [2024-11-08 14:16:13,263 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 119 states, 75 states have (on average 1.2133333333333334) internal successors, (91), 76 states have internal predecessors, (91), 35 states have call successors, (35), 8 states have call predecessors, (35), 8 states have return successors, (34), 34 states have call predecessors, (34), 34 states have call successors, (34) [2024-11-08 14:16:13,264 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 119 states to 119 states and 160 transitions. [2024-11-08 14:16:13,264 INFO L78 Accepts]: Start accepts. Automaton has 119 states and 160 transitions. Word has length 32 [2024-11-08 14:16:13,264 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:13,264 INFO L471 AbstractCegarLoop]: Abstraction has 119 states and 160 transitions. [2024-11-08 14:16:13,265 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-08 14:16:13,265 INFO L276 IsEmpty]: Start isEmpty. Operand 119 states and 160 transitions. [2024-11-08 14:16:13,265 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2024-11-08 14:16:13,265 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:13,266 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:13,266 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8 [2024-11-08 14:16:13,266 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:13,266 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:13,266 INFO L85 PathProgramCache]: Analyzing trace with hash -449167720, now seen corresponding path program 1 times [2024-11-08 14:16:13,266 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:13,266 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1130444202] [2024-11-08 14:16:13,267 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:13,267 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:13,274 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:16:13,274 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [577677288] [2024-11-08 14:16:13,274 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:13,275 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:13,275 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:16:13,276 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) [2024-11-08 14:16:13,291 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-08 14:16:13,319 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:13,320 INFO L255 TraceCheckSpWp]: Trace formula consists of 104 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-08 14:16:13,321 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:16:13,353 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-11-08 14:16:13,353 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-08 14:16:13,353 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:13,353 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1130444202] [2024-11-08 14:16:13,353 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:16:13,354 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [577677288] [2024-11-08 14:16:13,354 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [577677288] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:16:13,354 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:16:13,354 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-08 14:16:13,354 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [850290694] [2024-11-08 14:16:13,354 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:16:13,354 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:16:13,354 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:13,355 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:16:13,355 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-08 14:16:13,355 INFO L87 Difference]: Start difference. First operand 119 states and 160 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-08 14:16:13,402 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:13,402 INFO L93 Difference]: Finished difference Result 177 states and 257 transitions. [2024-11-08 14:16:13,402 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 14:16:13,402 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 37 [2024-11-08 14:16:13,402 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:13,403 INFO L225 Difference]: With dead ends: 177 [2024-11-08 14:16:13,403 INFO L226 Difference]: Without dead ends: 175 [2024-11-08 14:16:13,404 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 37 GetRequests, 33 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-08 14:16:13,404 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 4 mSDsluCounter, 80 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 112 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:13,404 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 112 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:16:13,405 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 175 states. [2024-11-08 14:16:13,426 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 175 to 163. [2024-11-08 14:16:13,427 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 163 states, 86 states have (on average 1.186046511627907) internal successors, (102), 95 states have internal predecessors, (102), 67 states have call successors, (67), 9 states have call predecessors, (67), 9 states have return successors, (66), 58 states have call predecessors, (66), 66 states have call successors, (66) [2024-11-08 14:16:13,428 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 163 states to 163 states and 235 transitions. [2024-11-08 14:16:13,428 INFO L78 Accepts]: Start accepts. Automaton has 163 states and 235 transitions. Word has length 37 [2024-11-08 14:16:13,428 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:13,429 INFO L471 AbstractCegarLoop]: Abstraction has 163 states and 235 transitions. [2024-11-08 14:16:13,429 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-08 14:16:13,429 INFO L276 IsEmpty]: Start isEmpty. Operand 163 states and 235 transitions. [2024-11-08 14:16:13,430 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2024-11-08 14:16:13,430 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:13,430 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:13,442 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2024-11-08 14:16:13,630 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:13,631 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:13,631 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:13,632 INFO L85 PathProgramCache]: Analyzing trace with hash 1289603446, now seen corresponding path program 1 times [2024-11-08 14:16:13,632 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:13,632 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [420821816] [2024-11-08 14:16:13,632 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:13,632 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:13,642 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:16:13,643 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [171152349] [2024-11-08 14:16:13,643 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:13,643 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:13,643 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:16:13,644 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) [2024-11-08 14:16:13,645 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-08 14:16:13,684 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:13,685 INFO L255 TraceCheckSpWp]: Trace formula consists of 135 conjuncts, 51 conjuncts are in the unsatisfiable core [2024-11-08 14:16:13,687 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:16:14,203 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 8 proven. 7 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2024-11-08 14:16:14,203 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:16:15,300 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 8 proven. 4 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-08 14:16:15,301 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:15,301 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [420821816] [2024-11-08 14:16:15,301 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:16:15,301 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [171152349] [2024-11-08 14:16:15,301 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [171152349] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:16:15,301 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 14:16:15,301 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 23 [2024-11-08 14:16:15,302 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1498377679] [2024-11-08 14:16:15,302 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 14:16:15,302 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-11-08 14:16:15,302 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:15,303 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-08 14:16:15,303 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=77, Invalid=429, Unknown=0, NotChecked=0, Total=506 [2024-11-08 14:16:15,303 INFO L87 Difference]: Start difference. First operand 163 states and 235 transitions. Second operand has 23 states, 21 states have (on average 2.0) internal successors, (42), 20 states have internal predecessors, (42), 6 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-11-08 14:16:18,549 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:18,549 INFO L93 Difference]: Finished difference Result 442 states and 660 transitions. [2024-11-08 14:16:18,553 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2024-11-08 14:16:18,553 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 21 states have (on average 2.0) internal successors, (42), 20 states have internal predecessors, (42), 6 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 49 [2024-11-08 14:16:18,554 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:18,557 INFO L225 Difference]: With dead ends: 442 [2024-11-08 14:16:18,557 INFO L226 Difference]: Without dead ends: 339 [2024-11-08 14:16:18,563 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 119 GetRequests, 75 SyntacticMatches, 0 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 432 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=398, Invalid=1672, Unknown=0, NotChecked=0, Total=2070 [2024-11-08 14:16:18,563 INFO L432 NwaCegarLoop]: 27 mSDtfsCounter, 174 mSDsluCounter, 307 mSDsCounter, 0 mSdLazyCounter, 565 mSolverCounterSat, 128 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 182 SdHoareTripleChecker+Valid, 334 SdHoareTripleChecker+Invalid, 693 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 128 IncrementalHoareTripleChecker+Valid, 565 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.9s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:18,564 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [182 Valid, 334 Invalid, 693 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [128 Valid, 565 Invalid, 0 Unknown, 0 Unchecked, 1.9s Time] [2024-11-08 14:16:18,564 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 339 states. [2024-11-08 14:16:18,647 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 339 to 253. [2024-11-08 14:16:18,648 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 253 states, 149 states have (on average 1.2080536912751678) internal successors, (180), 156 states have internal predecessors, (180), 91 states have call successors, (91), 12 states have call predecessors, (91), 12 states have return successors, (90), 84 states have call predecessors, (90), 90 states have call successors, (90) [2024-11-08 14:16:18,649 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 253 states to 253 states and 361 transitions. [2024-11-08 14:16:18,650 INFO L78 Accepts]: Start accepts. Automaton has 253 states and 361 transitions. Word has length 49 [2024-11-08 14:16:18,650 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:18,650 INFO L471 AbstractCegarLoop]: Abstraction has 253 states and 361 transitions. [2024-11-08 14:16:18,650 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 21 states have (on average 2.0) internal successors, (42), 20 states have internal predecessors, (42), 6 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-11-08 14:16:18,650 INFO L276 IsEmpty]: Start isEmpty. Operand 253 states and 361 transitions. [2024-11-08 14:16:18,651 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2024-11-08 14:16:18,651 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:18,651 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:18,666 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-11-08 14:16:18,852 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2024-11-08 14:16:18,853 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:18,853 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:18,853 INFO L85 PathProgramCache]: Analyzing trace with hash 982010905, now seen corresponding path program 1 times [2024-11-08 14:16:18,853 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:18,853 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [599468041] [2024-11-08 14:16:18,854 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:18,854 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:18,863 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:16:18,864 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [815353655] [2024-11-08 14:16:18,864 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:18,864 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:18,864 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:16:18,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) [2024-11-08 14:16:18,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 [2024-11-08 14:16:18,901 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:18,902 INFO L255 TraceCheckSpWp]: Trace formula consists of 146 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-08 14:16:18,903 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:16:18,953 INFO L134 CoverageAnalysis]: Checked inductivity of 107 backedges. 14 proven. 5 refuted. 0 times theorem prover too weak. 88 trivial. 0 not checked. [2024-11-08 14:16:18,954 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:16:18,998 INFO L134 CoverageAnalysis]: Checked inductivity of 107 backedges. 14 proven. 0 refuted. 0 times theorem prover too weak. 93 trivial. 0 not checked. [2024-11-08 14:16:18,998 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:18,999 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [599468041] [2024-11-08 14:16:18,999 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:16:18,999 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [815353655] [2024-11-08 14:16:18,999 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [815353655] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-08 14:16:18,999 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-08 14:16:18,999 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2024-11-08 14:16:18,999 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2114966938] [2024-11-08 14:16:18,999 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:16:18,999 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:16:18,999 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:19,000 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:16:19,000 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-08 14:16:19,000 INFO L87 Difference]: Start difference. First operand 253 states and 361 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2024-11-08 14:16:19,086 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:19,086 INFO L93 Difference]: Finished difference Result 259 states and 366 transitions. [2024-11-08 14:16:19,086 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 14:16:19,087 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 59 [2024-11-08 14:16:19,087 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:19,088 INFO L225 Difference]: With dead ends: 259 [2024-11-08 14:16:19,088 INFO L226 Difference]: Without dead ends: 257 [2024-11-08 14:16:19,089 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 117 GetRequests, 109 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-08 14:16:19,089 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 4 mSDsluCounter, 75 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 107 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:19,089 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 107 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:16:19,090 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 257 states. [2024-11-08 14:16:19,176 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 257 to 257. [2024-11-08 14:16:19,177 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 257 states, 152 states have (on average 1.2039473684210527) internal successors, (183), 159 states have internal predecessors, (183), 91 states have call successors, (91), 13 states have call predecessors, (91), 13 states have return successors, (90), 84 states have call predecessors, (90), 90 states have call successors, (90) [2024-11-08 14:16:19,178 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 257 states to 257 states and 364 transitions. [2024-11-08 14:16:19,178 INFO L78 Accepts]: Start accepts. Automaton has 257 states and 364 transitions. Word has length 59 [2024-11-08 14:16:19,179 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:19,179 INFO L471 AbstractCegarLoop]: Abstraction has 257 states and 364 transitions. [2024-11-08 14:16:19,179 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2024-11-08 14:16:19,179 INFO L276 IsEmpty]: Start isEmpty. Operand 257 states and 364 transitions. [2024-11-08 14:16:19,180 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2024-11-08 14:16:19,180 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:19,180 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:19,192 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-11-08 14:16:19,384 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:19,385 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:19,385 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:19,385 INFO L85 PathProgramCache]: Analyzing trace with hash -70799180, now seen corresponding path program 1 times [2024-11-08 14:16:19,386 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:19,386 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1504071655] [2024-11-08 14:16:19,386 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:19,386 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:19,398 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:16:19,399 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [542230147] [2024-11-08 14:16:19,399 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:19,399 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:19,399 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:16:19,403 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) [2024-11-08 14:16:19,403 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-08 14:16:19,443 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:19,444 INFO L255 TraceCheckSpWp]: Trace formula consists of 165 conjuncts, 43 conjuncts are in the unsatisfiable core [2024-11-08 14:16:19,446 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:16:19,772 INFO L134 CoverageAnalysis]: Checked inductivity of 57 backedges. 8 proven. 24 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2024-11-08 14:16:19,772 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:16:19,890 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:19,890 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1504071655] [2024-11-08 14:16:19,891 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:16:19,891 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [542230147] [2024-11-08 14:16:19,891 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [542230147] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:16:19,891 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-08 14:16:19,891 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2024-11-08 14:16:19,891 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [228092874] [2024-11-08 14:16:19,891 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-08 14:16:19,891 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-08 14:16:19,892 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:19,892 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-08 14:16:19,892 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=320, Unknown=0, NotChecked=0, Total=380 [2024-11-08 14:16:19,892 INFO L87 Difference]: Start difference. First operand 257 states and 364 transitions. Second operand has 15 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 13 states have internal predecessors, (35), 4 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 2 states have call predecessors, (6), 3 states have call successors, (6) [2024-11-08 14:16:20,386 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:20,386 INFO L93 Difference]: Finished difference Result 315 states and 451 transitions. [2024-11-08 14:16:20,388 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-11-08 14:16:20,388 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 13 states have internal predecessors, (35), 4 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 2 states have call predecessors, (6), 3 states have call successors, (6) Word has length 57 [2024-11-08 14:16:20,389 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:20,390 INFO L225 Difference]: With dead ends: 315 [2024-11-08 14:16:20,390 INFO L226 Difference]: Without dead ends: 313 [2024-11-08 14:16:20,391 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 78 GetRequests, 53 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 106 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=115, Invalid=587, Unknown=0, NotChecked=0, Total=702 [2024-11-08 14:16:20,391 INFO L432 NwaCegarLoop]: 58 mSDtfsCounter, 73 mSDsluCounter, 482 mSDsCounter, 0 mSdLazyCounter, 470 mSolverCounterSat, 35 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 89 SdHoareTripleChecker+Valid, 540 SdHoareTripleChecker+Invalid, 505 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 35 IncrementalHoareTripleChecker+Valid, 470 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:20,391 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [89 Valid, 540 Invalid, 505 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [35 Valid, 470 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-08 14:16:20,392 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 313 states. [2024-11-08 14:16:20,459 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 313 to 308. [2024-11-08 14:16:20,460 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 308 states, 178 states have (on average 1.2078651685393258) internal successors, (215), 188 states have internal predecessors, (215), 115 states have call successors, (115), 14 states have call predecessors, (115), 14 states have return successors, (114), 105 states have call predecessors, (114), 114 states have call successors, (114) [2024-11-08 14:16:20,461 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 308 states to 308 states and 444 transitions. [2024-11-08 14:16:20,462 INFO L78 Accepts]: Start accepts. Automaton has 308 states and 444 transitions. Word has length 57 [2024-11-08 14:16:20,462 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:20,462 INFO L471 AbstractCegarLoop]: Abstraction has 308 states and 444 transitions. [2024-11-08 14:16:20,462 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 13 states have internal predecessors, (35), 4 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 2 states have call predecessors, (6), 3 states have call successors, (6) [2024-11-08 14:16:20,462 INFO L276 IsEmpty]: Start isEmpty. Operand 308 states and 444 transitions. [2024-11-08 14:16:20,463 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2024-11-08 14:16:20,463 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:20,463 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:20,475 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2024-11-08 14:16:20,666 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2024-11-08 14:16:20,667 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:20,667 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:20,667 INFO L85 PathProgramCache]: Analyzing trace with hash 513336511, now seen corresponding path program 2 times [2024-11-08 14:16:20,667 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:20,667 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1542657594] [2024-11-08 14:16:20,667 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:20,667 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:20,696 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:20,743 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 14:16:20,743 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:20,744 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-08 14:16:20,744 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:20,745 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-11-08 14:16:20,746 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:20,747 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2024-11-08 14:16:20,748 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:20,750 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 33 [2024-11-08 14:16:20,750 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:20,752 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 38 [2024-11-08 14:16:20,752 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:20,754 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 48 [2024-11-08 14:16:20,754 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:20,755 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 53 [2024-11-08 14:16:20,756 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:20,757 INFO L134 CoverageAnalysis]: Checked inductivity of 88 backedges. 20 proven. 0 refuted. 0 times theorem prover too weak. 68 trivial. 0 not checked. [2024-11-08 14:16:20,757 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:20,757 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1542657594] [2024-11-08 14:16:20,757 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1542657594] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:16:20,757 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:16:20,757 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-08 14:16:20,757 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1143563664] [2024-11-08 14:16:20,757 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:16:20,758 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:16:20,758 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:20,758 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:16:20,758 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-08 14:16:20,758 INFO L87 Difference]: Start difference. First operand 308 states and 444 transitions. Second operand has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2024-11-08 14:16:20,900 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:20,900 INFO L93 Difference]: Finished difference Result 531 states and 768 transitions. [2024-11-08 14:16:20,901 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 14:16:20,901 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) Word has length 62 [2024-11-08 14:16:20,901 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:20,906 INFO L225 Difference]: With dead ends: 531 [2024-11-08 14:16:20,907 INFO L226 Difference]: Without dead ends: 317 [2024-11-08 14:16:20,907 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-08 14:16:20,908 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 1 mSDsluCounter, 69 mSDsCounter, 0 mSdLazyCounter, 43 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 101 SdHoareTripleChecker+Invalid, 44 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 43 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:20,908 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 101 Invalid, 44 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 43 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 14:16:20,908 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 317 states. [2024-11-08 14:16:20,992 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 317 to 305. [2024-11-08 14:16:20,994 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 305 states, 183 states have (on average 1.2076502732240437) internal successors, (221), 184 states have internal predecessors, (221), 107 states have call successors, (107), 14 states have call predecessors, (107), 14 states have return successors, (106), 106 states have call predecessors, (106), 106 states have call successors, (106) [2024-11-08 14:16:20,995 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 305 states to 305 states and 434 transitions. [2024-11-08 14:16:20,996 INFO L78 Accepts]: Start accepts. Automaton has 305 states and 434 transitions. Word has length 62 [2024-11-08 14:16:20,999 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:20,999 INFO L471 AbstractCegarLoop]: Abstraction has 305 states and 434 transitions. [2024-11-08 14:16:20,999 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2024-11-08 14:16:20,999 INFO L276 IsEmpty]: Start isEmpty. Operand 305 states and 434 transitions. [2024-11-08 14:16:20,999 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2024-11-08 14:16:21,000 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:21,000 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:21,000 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13 [2024-11-08 14:16:21,000 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:21,000 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:21,000 INFO L85 PathProgramCache]: Analyzing trace with hash -420355271, now seen corresponding path program 3 times [2024-11-08 14:16:21,000 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:21,000 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1968989826] [2024-11-08 14:16:21,000 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:21,000 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:21,019 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:16:21,025 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2072013219] [2024-11-08 14:16:21,029 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-08 14:16:21,029 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:21,029 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:16:21,030 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) [2024-11-08 14:16:21,031 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-08 14:16:21,137 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-08 14:16:21,137 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 14:16:21,138 INFO L255 TraceCheckSpWp]: Trace formula consists of 147 conjuncts, 55 conjuncts are in the unsatisfiable core [2024-11-08 14:16:21,140 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:16:21,922 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 10 proven. 22 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2024-11-08 14:16:21,922 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:16:23,052 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 14 proven. 18 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2024-11-08 14:16:23,052 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:23,052 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1968989826] [2024-11-08 14:16:23,052 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:16:23,052 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2072013219] [2024-11-08 14:16:23,053 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2072013219] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:16:23,053 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 14:16:23,053 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 13] total 23 [2024-11-08 14:16:23,053 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1858459915] [2024-11-08 14:16:23,054 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 14:16:23,054 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-11-08 14:16:23,054 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:23,054 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-08 14:16:23,055 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=97, Invalid=409, Unknown=0, NotChecked=0, Total=506 [2024-11-08 14:16:23,055 INFO L87 Difference]: Start difference. First operand 305 states and 434 transitions. Second operand has 23 states, 23 states have (on average 2.3043478260869565) internal successors, (53), 22 states have internal predecessors, (53), 5 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (12), 5 states have call predecessors, (12), 5 states have call successors, (12) [2024-11-08 14:16:27,056 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:27,056 INFO L93 Difference]: Finished difference Result 403 states and 561 transitions. [2024-11-08 14:16:27,057 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2024-11-08 14:16:27,057 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 2.3043478260869565) internal successors, (53), 22 states have internal predecessors, (53), 5 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (12), 5 states have call predecessors, (12), 5 states have call successors, (12) Word has length 62 [2024-11-08 14:16:27,057 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:27,059 INFO L225 Difference]: With dead ends: 403 [2024-11-08 14:16:27,059 INFO L226 Difference]: Without dead ends: 401 [2024-11-08 14:16:27,060 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 147 GetRequests, 99 SyntacticMatches, 2 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 485 ImplicationChecksByTransitivity, 2.7s TimeCoverageRelationStatistics Valid=488, Invalid=1768, Unknown=0, NotChecked=0, Total=2256 [2024-11-08 14:16:27,061 INFO L432 NwaCegarLoop]: 40 mSDtfsCounter, 248 mSDsluCounter, 307 mSDsCounter, 0 mSdLazyCounter, 482 mSolverCounterSat, 206 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 248 SdHoareTripleChecker+Valid, 347 SdHoareTripleChecker+Invalid, 688 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 206 IncrementalHoareTripleChecker+Valid, 482 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.9s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:27,061 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [248 Valid, 347 Invalid, 688 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [206 Valid, 482 Invalid, 0 Unknown, 0 Unchecked, 1.9s Time] [2024-11-08 14:16:27,061 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 401 states. [2024-11-08 14:16:27,180 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 401 to 379. [2024-11-08 14:16:27,181 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 379 states, 229 states have (on average 1.205240174672489) internal successors, (276), 230 states have internal predecessors, (276), 131 states have call successors, (131), 18 states have call predecessors, (131), 18 states have return successors, (130), 130 states have call predecessors, (130), 130 states have call successors, (130) [2024-11-08 14:16:27,182 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 379 states to 379 states and 537 transitions. [2024-11-08 14:16:27,183 INFO L78 Accepts]: Start accepts. Automaton has 379 states and 537 transitions. Word has length 62 [2024-11-08 14:16:27,183 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:27,183 INFO L471 AbstractCegarLoop]: Abstraction has 379 states and 537 transitions. [2024-11-08 14:16:27,183 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 2.3043478260869565) internal successors, (53), 22 states have internal predecessors, (53), 5 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (12), 5 states have call predecessors, (12), 5 states have call successors, (12) [2024-11-08 14:16:27,183 INFO L276 IsEmpty]: Start isEmpty. Operand 379 states and 537 transitions. [2024-11-08 14:16:27,184 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 77 [2024-11-08 14:16:27,184 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:27,184 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:27,191 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-11-08 14:16:27,387 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2024-11-08 14:16:27,388 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:27,388 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:27,388 INFO L85 PathProgramCache]: Analyzing trace with hash -819166674, now seen corresponding path program 1 times [2024-11-08 14:16:27,388 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:27,388 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1189477682] [2024-11-08 14:16:27,388 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:27,388 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:27,408 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:16:27,409 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1780519186] [2024-11-08 14:16:27,409 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:27,409 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:27,409 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:16:27,414 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) [2024-11-08 14:16:27,415 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-08 14:16:27,462 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:27,464 INFO L255 TraceCheckSpWp]: Trace formula consists of 197 conjuncts, 77 conjuncts are in the unsatisfiable core [2024-11-08 14:16:27,466 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:16:28,229 INFO L134 CoverageAnalysis]: Checked inductivity of 151 backedges. 30 proven. 29 refuted. 0 times theorem prover too weak. 92 trivial. 0 not checked. [2024-11-08 14:16:28,229 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:16:30,902 INFO L134 CoverageAnalysis]: Checked inductivity of 151 backedges. 30 proven. 26 refuted. 0 times theorem prover too weak. 95 trivial. 0 not checked. [2024-11-08 14:16:30,903 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:30,903 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1189477682] [2024-11-08 14:16:30,903 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:16:30,903 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1780519186] [2024-11-08 14:16:30,903 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1780519186] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:16:30,903 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 14:16:30,903 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 16] total 33 [2024-11-08 14:16:30,904 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [27101160] [2024-11-08 14:16:30,904 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 14:16:30,904 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2024-11-08 14:16:30,904 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:30,905 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2024-11-08 14:16:30,905 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=151, Invalid=905, Unknown=0, NotChecked=0, Total=1056 [2024-11-08 14:16:30,905 INFO L87 Difference]: Start difference. First operand 379 states and 537 transitions. Second operand has 33 states, 31 states have (on average 1.967741935483871) internal successors, (61), 31 states have internal predecessors, (61), 9 states have call successors, (21), 3 states have call predecessors, (21), 3 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) [2024-11-08 14:16:41,095 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:41,096 INFO L93 Difference]: Finished difference Result 573 states and 828 transitions. [2024-11-08 14:16:41,096 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 58 states. [2024-11-08 14:16:41,096 INFO L78 Accepts]: Start accepts. Automaton has has 33 states, 31 states have (on average 1.967741935483871) internal successors, (61), 31 states have internal predecessors, (61), 9 states have call successors, (21), 3 states have call predecessors, (21), 3 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) Word has length 76 [2024-11-08 14:16:41,097 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:41,099 INFO L225 Difference]: With dead ends: 573 [2024-11-08 14:16:41,099 INFO L226 Difference]: Without dead ends: 569 [2024-11-08 14:16:41,100 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 196 GetRequests, 119 SyntacticMatches, 0 SemanticMatches, 77 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1580 ImplicationChecksByTransitivity, 7.9s TimeCoverageRelationStatistics Valid=1200, Invalid=4962, Unknown=0, NotChecked=0, Total=6162 [2024-11-08 14:16:41,101 INFO L432 NwaCegarLoop]: 47 mSDtfsCounter, 274 mSDsluCounter, 717 mSDsCounter, 0 mSdLazyCounter, 1165 mSolverCounterSat, 362 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 274 SdHoareTripleChecker+Valid, 764 SdHoareTripleChecker+Invalid, 1527 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 362 IncrementalHoareTripleChecker+Valid, 1165 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.8s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:41,101 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [274 Valid, 764 Invalid, 1527 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [362 Valid, 1165 Invalid, 0 Unknown, 0 Unchecked, 3.8s Time] [2024-11-08 14:16:41,101 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 569 states. [2024-11-08 14:16:41,402 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 569 to 523. [2024-11-08 14:16:41,403 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 523 states, 318 states have (on average 1.220125786163522) internal successors, (388), 319 states have internal predecessors, (388), 183 states have call successors, (183), 21 states have call predecessors, (183), 21 states have return successors, (182), 182 states have call predecessors, (182), 182 states have call successors, (182) [2024-11-08 14:16:41,404 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 523 states to 523 states and 753 transitions. [2024-11-08 14:16:41,405 INFO L78 Accepts]: Start accepts. Automaton has 523 states and 753 transitions. Word has length 76 [2024-11-08 14:16:41,405 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:41,405 INFO L471 AbstractCegarLoop]: Abstraction has 523 states and 753 transitions. [2024-11-08 14:16:41,406 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 33 states, 31 states have (on average 1.967741935483871) internal successors, (61), 31 states have internal predecessors, (61), 9 states have call successors, (21), 3 states have call predecessors, (21), 3 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) [2024-11-08 14:16:41,406 INFO L276 IsEmpty]: Start isEmpty. Operand 523 states and 753 transitions. [2024-11-08 14:16:41,406 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2024-11-08 14:16:41,406 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:41,406 INFO L215 NwaCegarLoop]: trace histogram [11, 10, 10, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:41,419 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2024-11-08 14:16:41,607 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2024-11-08 14:16:41,607 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:41,607 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:41,607 INFO L85 PathProgramCache]: Analyzing trace with hash 685229769, now seen corresponding path program 1 times [2024-11-08 14:16:41,607 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:41,607 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1000738087] [2024-11-08 14:16:41,607 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:41,608 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:41,616 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:16:41,616 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [138404010] [2024-11-08 14:16:41,616 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:41,616 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:41,616 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:16:41,619 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) [2024-11-08 14:16:41,620 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-11-08 14:16:41,660 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:41,661 INFO L255 TraceCheckSpWp]: Trace formula consists of 185 conjuncts, 31 conjuncts are in the unsatisfiable core [2024-11-08 14:16:41,662 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:16:41,855 INFO L134 CoverageAnalysis]: Checked inductivity of 220 backedges. 20 proven. 19 refuted. 0 times theorem prover too weak. 181 trivial. 0 not checked. [2024-11-08 14:16:41,855 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:16:42,236 INFO L134 CoverageAnalysis]: Checked inductivity of 220 backedges. 22 proven. 14 refuted. 0 times theorem prover too weak. 184 trivial. 0 not checked. [2024-11-08 14:16:42,237 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:42,237 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1000738087] [2024-11-08 14:16:42,237 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:16:42,237 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [138404010] [2024-11-08 14:16:42,237 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [138404010] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:16:42,237 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 14:16:42,237 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 21 [2024-11-08 14:16:42,237 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1072034677] [2024-11-08 14:16:42,238 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 14:16:42,238 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-08 14:16:42,238 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:42,238 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-08 14:16:42,239 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=81, Invalid=339, Unknown=0, NotChecked=0, Total=420 [2024-11-08 14:16:42,239 INFO L87 Difference]: Start difference. First operand 523 states and 753 transitions. Second operand has 21 states, 21 states have (on average 1.9523809523809523) internal successors, (41), 18 states have internal predecessors, (41), 8 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2024-11-08 14:16:43,828 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:43,828 INFO L93 Difference]: Finished difference Result 1078 states and 1682 transitions. [2024-11-08 14:16:43,831 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2024-11-08 14:16:43,831 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 1.9523809523809523) internal successors, (41), 18 states have internal predecessors, (41), 8 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) Word has length 79 [2024-11-08 14:16:43,832 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:43,836 INFO L225 Difference]: With dead ends: 1078 [2024-11-08 14:16:43,836 INFO L226 Difference]: Without dead ends: 1076 [2024-11-08 14:16:43,837 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 175 GetRequests, 137 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 317 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=345, Invalid=1215, Unknown=0, NotChecked=0, Total=1560 [2024-11-08 14:16:43,837 INFO L432 NwaCegarLoop]: 40 mSDtfsCounter, 128 mSDsluCounter, 310 mSDsCounter, 0 mSdLazyCounter, 333 mSolverCounterSat, 122 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 132 SdHoareTripleChecker+Valid, 350 SdHoareTripleChecker+Invalid, 455 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 122 IncrementalHoareTripleChecker+Valid, 333 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:43,837 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [132 Valid, 350 Invalid, 455 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [122 Valid, 333 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-08 14:16:43,838 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1076 states. [2024-11-08 14:16:44,570 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1076 to 1016. [2024-11-08 14:16:44,572 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1016 states, 515 states have (on average 1.3029126213592233) internal successors, (671), 516 states have internal predecessors, (671), 475 states have call successors, (475), 25 states have call predecessors, (475), 25 states have return successors, (474), 474 states have call predecessors, (474), 474 states have call successors, (474) [2024-11-08 14:16:44,576 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1016 states to 1016 states and 1620 transitions. [2024-11-08 14:16:44,578 INFO L78 Accepts]: Start accepts. Automaton has 1016 states and 1620 transitions. Word has length 79 [2024-11-08 14:16:44,578 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:44,579 INFO L471 AbstractCegarLoop]: Abstraction has 1016 states and 1620 transitions. [2024-11-08 14:16:44,579 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 1.9523809523809523) internal successors, (41), 18 states have internal predecessors, (41), 8 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2024-11-08 14:16:44,579 INFO L276 IsEmpty]: Start isEmpty. Operand 1016 states and 1620 transitions. [2024-11-08 14:16:44,580 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2024-11-08 14:16:44,580 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:44,580 INFO L215 NwaCegarLoop]: trace histogram [10, 9, 9, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:44,593 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2024-11-08 14:16:44,780 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2024-11-08 14:16:44,781 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:44,781 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:44,781 INFO L85 PathProgramCache]: Analyzing trace with hash -248462013, now seen corresponding path program 1 times [2024-11-08 14:16:44,781 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:44,781 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2146818426] [2024-11-08 14:16:44,781 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:44,781 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:44,792 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:16:44,792 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [878691948] [2024-11-08 14:16:44,792 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:44,793 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:44,793 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:16:44,794 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) [2024-11-08 14:16:44,795 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2024-11-08 14:16:44,840 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:16:44,841 INFO L255 TraceCheckSpWp]: Trace formula consists of 196 conjuncts, 47 conjuncts are in the unsatisfiable core [2024-11-08 14:16:44,842 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:16:45,348 INFO L134 CoverageAnalysis]: Checked inductivity of 186 backedges. 18 proven. 23 refuted. 0 times theorem prover too weak. 145 trivial. 0 not checked. [2024-11-08 14:16:45,348 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:16:46,277 INFO L134 CoverageAnalysis]: Checked inductivity of 186 backedges. 18 proven. 20 refuted. 0 times theorem prover too weak. 148 trivial. 0 not checked. [2024-11-08 14:16:46,278 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:46,278 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2146818426] [2024-11-08 14:16:46,278 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:16:46,278 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [878691948] [2024-11-08 14:16:46,278 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [878691948] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:16:46,278 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 14:16:46,278 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 23 [2024-11-08 14:16:46,278 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [624499067] [2024-11-08 14:16:46,278 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 14:16:46,279 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-11-08 14:16:46,279 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:46,279 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-08 14:16:46,279 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=80, Invalid=426, Unknown=0, NotChecked=0, Total=506 [2024-11-08 14:16:46,280 INFO L87 Difference]: Start difference. First operand 1016 states and 1620 transitions. Second operand has 23 states, 23 states have (on average 2.260869565217391) internal successors, (52), 20 states have internal predecessors, (52), 8 states have call successors, (23), 3 states have call predecessors, (23), 2 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) [2024-11-08 14:16:54,709 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:16:54,710 INFO L93 Difference]: Finished difference Result 1403 states and 2248 transitions. [2024-11-08 14:16:54,710 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 44 states. [2024-11-08 14:16:54,710 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 2.260869565217391) internal successors, (52), 20 states have internal predecessors, (52), 8 states have call successors, (23), 3 states have call predecessors, (23), 2 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) Word has length 79 [2024-11-08 14:16:54,710 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:16:54,717 INFO L225 Difference]: With dead ends: 1403 [2024-11-08 14:16:54,717 INFO L226 Difference]: Without dead ends: 1401 [2024-11-08 14:16:54,718 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 193 GetRequests, 135 SyntacticMatches, 0 SemanticMatches, 58 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 782 ImplicationChecksByTransitivity, 4.3s TimeCoverageRelationStatistics Valid=711, Invalid=2829, Unknown=0, NotChecked=0, Total=3540 [2024-11-08 14:16:54,718 INFO L432 NwaCegarLoop]: 49 mSDtfsCounter, 164 mSDsluCounter, 464 mSDsCounter, 0 mSdLazyCounter, 746 mSolverCounterSat, 166 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 164 SdHoareTripleChecker+Valid, 513 SdHoareTripleChecker+Invalid, 912 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 166 IncrementalHoareTripleChecker+Valid, 746 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.4s IncrementalHoareTripleChecker+Time [2024-11-08 14:16:54,718 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [164 Valid, 513 Invalid, 912 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [166 Valid, 746 Invalid, 0 Unknown, 0 Unchecked, 3.4s Time] [2024-11-08 14:16:54,719 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1401 states. [2024-11-08 14:16:55,860 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1401 to 1273. [2024-11-08 14:16:55,862 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1273 states, 641 states have (on average 1.3104524180967239) internal successors, (840), 642 states have internal predecessors, (840), 603 states have call successors, (603), 28 states have call predecessors, (603), 28 states have return successors, (602), 602 states have call predecessors, (602), 602 states have call successors, (602) [2024-11-08 14:16:55,867 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1273 states to 1273 states and 2045 transitions. [2024-11-08 14:16:55,869 INFO L78 Accepts]: Start accepts. Automaton has 1273 states and 2045 transitions. Word has length 79 [2024-11-08 14:16:55,869 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:16:55,869 INFO L471 AbstractCegarLoop]: Abstraction has 1273 states and 2045 transitions. [2024-11-08 14:16:55,869 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 2.260869565217391) internal successors, (52), 20 states have internal predecessors, (52), 8 states have call successors, (23), 3 states have call predecessors, (23), 2 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) [2024-11-08 14:16:55,869 INFO L276 IsEmpty]: Start isEmpty. Operand 1273 states and 2045 transitions. [2024-11-08 14:16:55,870 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 83 [2024-11-08 14:16:55,873 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:16:55,873 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 5, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:16:55,885 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2024-11-08 14:16:56,076 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable17,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:56,077 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:16:56,077 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:16:56,077 INFO L85 PathProgramCache]: Analyzing trace with hash -431606335, now seen corresponding path program 4 times [2024-11-08 14:16:56,077 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:16:56,077 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [225275667] [2024-11-08 14:16:56,077 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:16:56,077 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:16:56,099 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:16:56,099 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [221577187] [2024-11-08 14:16:56,099 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-08 14:16:56,100 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:16:56,100 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:16:56,104 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) [2024-11-08 14:16:56,109 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2024-11-08 14:16:56,154 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-08 14:16:56,154 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 14:16:56,159 INFO L255 TraceCheckSpWp]: Trace formula consists of 190 conjuncts, 41 conjuncts are in the unsatisfiable core [2024-11-08 14:16:56,160 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:16:56,898 INFO L134 CoverageAnalysis]: Checked inductivity of 170 backedges. 30 proven. 45 refuted. 0 times theorem prover too weak. 95 trivial. 0 not checked. [2024-11-08 14:16:56,899 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:16:57,197 INFO L134 CoverageAnalysis]: Checked inductivity of 170 backedges. 55 proven. 9 refuted. 0 times theorem prover too weak. 106 trivial. 0 not checked. [2024-11-08 14:16:57,198 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:16:57,198 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [225275667] [2024-11-08 14:16:57,198 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:16:57,198 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [221577187] [2024-11-08 14:16:57,198 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [221577187] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:16:57,198 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 14:16:57,198 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 9] total 21 [2024-11-08 14:16:57,198 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1208287351] [2024-11-08 14:16:57,199 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 14:16:57,199 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-08 14:16:57,199 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:16:57,199 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-08 14:16:57,200 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=65, Invalid=355, Unknown=0, NotChecked=0, Total=420 [2024-11-08 14:16:57,200 INFO L87 Difference]: Start difference. First operand 1273 states and 2045 transitions. Second operand has 21 states, 21 states have (on average 2.9523809523809526) internal successors, (62), 18 states have internal predecessors, (62), 7 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (17), 5 states have call predecessors, (17), 5 states have call successors, (17) [2024-11-08 14:17:00,528 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:17:00,528 INFO L93 Difference]: Finished difference Result 1392 states and 2226 transitions. [2024-11-08 14:17:00,529 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2024-11-08 14:17:00,529 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 2.9523809523809526) internal successors, (62), 18 states have internal predecessors, (62), 7 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (17), 5 states have call predecessors, (17), 5 states have call successors, (17) Word has length 82 [2024-11-08 14:17:00,530 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:17:00,536 INFO L225 Difference]: With dead ends: 1392 [2024-11-08 14:17:00,536 INFO L226 Difference]: Without dead ends: 1390 [2024-11-08 14:17:00,537 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 184 GetRequests, 147 SyntacticMatches, 2 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 235 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=213, Invalid=1119, Unknown=0, NotChecked=0, Total=1332 [2024-11-08 14:17:00,538 INFO L432 NwaCegarLoop]: 48 mSDtfsCounter, 75 mSDsluCounter, 482 mSDsCounter, 0 mSdLazyCounter, 545 mSolverCounterSat, 52 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 79 SdHoareTripleChecker+Valid, 530 SdHoareTripleChecker+Invalid, 597 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 52 IncrementalHoareTripleChecker+Valid, 545 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.2s IncrementalHoareTripleChecker+Time [2024-11-08 14:17:00,538 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [79 Valid, 530 Invalid, 597 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [52 Valid, 545 Invalid, 0 Unknown, 0 Unchecked, 1.2s Time] [2024-11-08 14:17:00,539 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1390 states. [2024-11-08 14:17:01,749 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1390 to 1297. [2024-11-08 14:17:01,751 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1297 states, 659 states have (on average 1.3019726858877088) internal successors, (858), 660 states have internal predecessors, (858), 603 states have call successors, (603), 34 states have call predecessors, (603), 34 states have return successors, (602), 602 states have call predecessors, (602), 602 states have call successors, (602) [2024-11-08 14:17:01,755 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1297 states to 1297 states and 2063 transitions. [2024-11-08 14:17:01,757 INFO L78 Accepts]: Start accepts. Automaton has 1297 states and 2063 transitions. Word has length 82 [2024-11-08 14:17:01,757 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:17:01,757 INFO L471 AbstractCegarLoop]: Abstraction has 1297 states and 2063 transitions. [2024-11-08 14:17:01,757 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 2.9523809523809526) internal successors, (62), 18 states have internal predecessors, (62), 7 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (17), 5 states have call predecessors, (17), 5 states have call successors, (17) [2024-11-08 14:17:01,757 INFO L276 IsEmpty]: Start isEmpty. Operand 1297 states and 2063 transitions. [2024-11-08 14:17:01,758 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 85 [2024-11-08 14:17:01,758 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:17:01,759 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 5, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:17:01,772 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Ended with exit code 0 [2024-11-08 14:17:01,962 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:17:01,963 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:17:01,963 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:17:01,963 INFO L85 PathProgramCache]: Analyzing trace with hash -1959088841, now seen corresponding path program 2 times [2024-11-08 14:17:01,963 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:17:01,963 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1023172069] [2024-11-08 14:17:01,963 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:17:01,963 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:17:01,982 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:17:02,104 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 14:17:02,105 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:17:02,106 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-08 14:17:02,106 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:17:02,107 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-11-08 14:17:02,107 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:17:02,111 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2024-11-08 14:17:02,112 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:17:02,113 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 33 [2024-11-08 14:17:02,114 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:17:02,115 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 38 [2024-11-08 14:17:02,116 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:17:02,117 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 53 [2024-11-08 14:17:02,120 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:17:02,121 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 58 [2024-11-08 14:17:02,122 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:17:02,124 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 63 [2024-11-08 14:17:02,124 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:17:02,127 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 68 [2024-11-08 14:17:02,129 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:17:02,132 INFO L134 CoverageAnalysis]: Checked inductivity of 174 backedges. 38 proven. 16 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2024-11-08 14:17:02,136 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:17:02,136 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1023172069] [2024-11-08 14:17:02,136 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1023172069] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:17:02,136 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1502697548] [2024-11-08 14:17:02,136 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-08 14:17:02,137 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:17:02,137 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:17:02,141 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) [2024-11-08 14:17:02,143 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2024-11-08 14:17:02,207 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-08 14:17:02,208 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 14:17:02,208 INFO L255 TraceCheckSpWp]: Trace formula consists of 223 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-08 14:17:02,209 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:17:02,259 INFO L134 CoverageAnalysis]: Checked inductivity of 174 backedges. 38 proven. 16 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2024-11-08 14:17:02,259 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:17:02,340 INFO L134 CoverageAnalysis]: Checked inductivity of 174 backedges. 38 proven. 16 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2024-11-08 14:17:02,341 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1502697548] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:17:02,341 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 14:17:02,341 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10, 10] total 11 [2024-11-08 14:17:02,341 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [462415976] [2024-11-08 14:17:02,341 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 14:17:02,341 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-11-08 14:17:02,342 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:17:02,342 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-08 14:17:02,342 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=89, Unknown=0, NotChecked=0, Total=110 [2024-11-08 14:17:02,342 INFO L87 Difference]: Start difference. First operand 1297 states and 2063 transitions. Second operand has 11 states, 11 states have (on average 3.4545454545454546) internal successors, (38), 11 states have internal predecessors, (38), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2024-11-08 14:17:03,809 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:17:03,810 INFO L93 Difference]: Finished difference Result 1432 states and 2271 transitions. [2024-11-08 14:17:03,810 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2024-11-08 14:17:03,810 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 3.4545454545454546) internal successors, (38), 11 states have internal predecessors, (38), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) Word has length 84 [2024-11-08 14:17:03,811 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:17:03,817 INFO L225 Difference]: With dead ends: 1432 [2024-11-08 14:17:03,817 INFO L226 Difference]: Without dead ends: 1425 [2024-11-08 14:17:03,817 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 216 GetRequests, 185 SyntacticMatches, 8 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 96 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=141, Invalid=459, Unknown=0, NotChecked=0, Total=600 [2024-11-08 14:17:03,818 INFO L432 NwaCegarLoop]: 54 mSDtfsCounter, 66 mSDsluCounter, 291 mSDsCounter, 0 mSdLazyCounter, 254 mSolverCounterSat, 57 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 70 SdHoareTripleChecker+Valid, 345 SdHoareTripleChecker+Invalid, 311 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 57 IncrementalHoareTripleChecker+Valid, 254 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-08 14:17:03,818 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [70 Valid, 345 Invalid, 311 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [57 Valid, 254 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-08 14:17:03,819 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1425 states. [2024-11-08 14:17:04,973 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1425 to 1252. [2024-11-08 14:17:04,975 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1252 states, 626 states have (on average 1.3083067092651757) internal successors, (819), 627 states have internal predecessors, (819), 591 states have call successors, (591), 34 states have call predecessors, (591), 34 states have return successors, (590), 590 states have call predecessors, (590), 590 states have call successors, (590) [2024-11-08 14:17:04,979 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1252 states to 1252 states and 2000 transitions. [2024-11-08 14:17:04,980 INFO L78 Accepts]: Start accepts. Automaton has 1252 states and 2000 transitions. Word has length 84 [2024-11-08 14:17:04,980 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:17:04,981 INFO L471 AbstractCegarLoop]: Abstraction has 1252 states and 2000 transitions. [2024-11-08 14:17:04,981 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 3.4545454545454546) internal successors, (38), 11 states have internal predecessors, (38), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2024-11-08 14:17:04,981 INFO L276 IsEmpty]: Start isEmpty. Operand 1252 states and 2000 transitions. [2024-11-08 14:17:04,982 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2024-11-08 14:17:04,982 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:17:04,982 INFO L215 NwaCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:17:04,994 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2024-11-08 14:17:05,186 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:17:05,186 INFO L396 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:17:05,187 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:17:05,187 INFO L85 PathProgramCache]: Analyzing trace with hash 1810606754, now seen corresponding path program 2 times [2024-11-08 14:17:05,187 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:17:05,187 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1429636985] [2024-11-08 14:17:05,187 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:17:05,187 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:17:05,196 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:17:05,197 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [635779591] [2024-11-08 14:17:05,197 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-08 14:17:05,197 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:17:05,197 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:17:05,199 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) [2024-11-08 14:17:05,204 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2024-11-08 14:17:05,252 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-08 14:17:05,252 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 14:17:05,253 INFO L255 TraceCheckSpWp]: Trace formula consists of 225 conjuncts, 51 conjuncts are in the unsatisfiable core [2024-11-08 14:17:05,255 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:17:05,938 INFO L134 CoverageAnalysis]: Checked inductivity of 319 backedges. 24 proven. 27 refuted. 0 times theorem prover too weak. 268 trivial. 0 not checked. [2024-11-08 14:17:05,938 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:17:08,055 INFO L134 CoverageAnalysis]: Checked inductivity of 319 backedges. 24 proven. 27 refuted. 0 times theorem prover too weak. 268 trivial. 0 not checked. [2024-11-08 14:17:08,055 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:17:08,055 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1429636985] [2024-11-08 14:17:08,056 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:17:08,056 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [635779591] [2024-11-08 14:17:08,056 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [635779591] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:17:08,056 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 14:17:08,056 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 24 [2024-11-08 14:17:08,056 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [427625686] [2024-11-08 14:17:08,056 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 14:17:08,057 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2024-11-08 14:17:08,057 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:17:08,057 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2024-11-08 14:17:08,057 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=86, Invalid=466, Unknown=0, NotChecked=0, Total=552 [2024-11-08 14:17:08,057 INFO L87 Difference]: Start difference. First operand 1252 states and 2000 transitions. Second operand has 24 states, 22 states have (on average 2.3181818181818183) internal successors, (51), 23 states have internal predecessors, (51), 9 states have call successors, (28), 2 states have call predecessors, (28), 1 states have return successors, (26), 7 states have call predecessors, (26), 7 states have call successors, (26) [2024-11-08 14:17:20,736 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:17:20,736 INFO L93 Difference]: Finished difference Result 1956 states and 3175 transitions. [2024-11-08 14:17:20,736 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 89 states. [2024-11-08 14:17:20,736 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 22 states have (on average 2.3181818181818183) internal successors, (51), 23 states have internal predecessors, (51), 9 states have call successors, (28), 2 states have call predecessors, (28), 1 states have return successors, (26), 7 states have call predecessors, (26), 7 states have call successors, (26) Word has length 96 [2024-11-08 14:17:20,737 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:17:20,745 INFO L225 Difference]: With dead ends: 1956 [2024-11-08 14:17:20,745 INFO L226 Difference]: Without dead ends: 1948 [2024-11-08 14:17:20,747 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 267 GetRequests, 166 SyntacticMatches, 2 SemanticMatches, 99 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3253 ImplicationChecksByTransitivity, 7.9s TimeCoverageRelationStatistics Valid=1436, Invalid=8664, Unknown=0, NotChecked=0, Total=10100 [2024-11-08 14:17:20,748 INFO L432 NwaCegarLoop]: 66 mSDtfsCounter, 227 mSDsluCounter, 658 mSDsCounter, 0 mSdLazyCounter, 993 mSolverCounterSat, 239 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 243 SdHoareTripleChecker+Valid, 724 SdHoareTripleChecker+Invalid, 1232 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 239 IncrementalHoareTripleChecker+Valid, 993 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:17:20,748 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [243 Valid, 724 Invalid, 1232 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [239 Valid, 993 Invalid, 0 Unknown, 0 Unchecked, 4.0s Time] [2024-11-08 14:17:20,749 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1948 states. [2024-11-08 14:17:22,151 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1948 to 1392. [2024-11-08 14:17:22,154 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1392 states, 693 states have (on average 1.3116883116883118) internal successors, (909), 694 states have internal predecessors, (909), 663 states have call successors, (663), 35 states have call predecessors, (663), 35 states have return successors, (662), 662 states have call predecessors, (662), 662 states have call successors, (662) [2024-11-08 14:17:22,158 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1392 states to 1392 states and 2234 transitions. [2024-11-08 14:17:22,160 INFO L78 Accepts]: Start accepts. Automaton has 1392 states and 2234 transitions. Word has length 96 [2024-11-08 14:17:22,160 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:17:22,160 INFO L471 AbstractCegarLoop]: Abstraction has 1392 states and 2234 transitions. [2024-11-08 14:17:22,160 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 22 states have (on average 2.3181818181818183) internal successors, (51), 23 states have internal predecessors, (51), 9 states have call successors, (28), 2 states have call predecessors, (28), 1 states have return successors, (26), 7 states have call predecessors, (26), 7 states have call successors, (26) [2024-11-08 14:17:22,160 INFO L276 IsEmpty]: Start isEmpty. Operand 1392 states and 2234 transitions. [2024-11-08 14:17:22,162 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 107 [2024-11-08 14:17:22,162 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:17:22,162 INFO L215 NwaCegarLoop]: trace histogram [14, 13, 13, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:17:22,178 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Ended with exit code 0 [2024-11-08 14:17:22,362 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20,18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:17:22,363 INFO L396 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:17:22,363 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:17:22,363 INFO L85 PathProgramCache]: Analyzing trace with hash 1312648187, now seen corresponding path program 2 times [2024-11-08 14:17:22,363 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:17:22,364 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1699744840] [2024-11-08 14:17:22,364 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:17:22,364 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:17:22,383 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:17:22,387 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [664711598] [2024-11-08 14:17:22,388 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-08 14:17:22,388 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:17:22,388 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:17:22,391 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:17:22,394 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2024-11-08 14:17:22,447 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-08 14:17:22,447 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 14:17:22,448 INFO L255 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 73 conjuncts are in the unsatisfiable core [2024-11-08 14:17:22,450 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:17:23,274 INFO L134 CoverageAnalysis]: Checked inductivity of 388 backedges. 52 proven. 59 refuted. 0 times theorem prover too weak. 277 trivial. 0 not checked. [2024-11-08 14:17:23,274 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:17:27,583 INFO L134 CoverageAnalysis]: Checked inductivity of 388 backedges. 56 proven. 52 refuted. 0 times theorem prover too weak. 280 trivial. 0 not checked. [2024-11-08 14:17:27,583 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:17:27,584 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1699744840] [2024-11-08 14:17:27,584 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:17:27,584 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [664711598] [2024-11-08 14:17:27,584 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [664711598] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:17:27,584 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 14:17:27,584 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 17] total 34 [2024-11-08 14:17:27,584 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1141339800] [2024-11-08 14:17:27,584 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 14:17:27,585 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 34 states [2024-11-08 14:17:27,585 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:17:27,585 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2024-11-08 14:17:27,585 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=168, Invalid=954, Unknown=0, NotChecked=0, Total=1122 [2024-11-08 14:17:27,586 INFO L87 Difference]: Start difference. First operand 1392 states and 2234 transitions. Second operand has 34 states, 34 states have (on average 2.088235294117647) internal successors, (71), 32 states have internal predecessors, (71), 11 states have call successors, (31), 3 states have call predecessors, (31), 3 states have return successors, (30), 11 states have call predecessors, (30), 11 states have call successors, (30) [2024-11-08 14:17:46,342 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:17:46,344 INFO L93 Difference]: Finished difference Result 1641 states and 2590 transitions. [2024-11-08 14:17:46,344 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 63 states. [2024-11-08 14:17:46,344 INFO L78 Accepts]: Start accepts. Automaton has has 34 states, 34 states have (on average 2.088235294117647) internal successors, (71), 32 states have internal predecessors, (71), 11 states have call successors, (31), 3 states have call predecessors, (31), 3 states have return successors, (30), 11 states have call predecessors, (30), 11 states have call successors, (30) Word has length 106 [2024-11-08 14:17:46,346 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:17:46,353 INFO L225 Difference]: With dead ends: 1641 [2024-11-08 14:17:46,353 INFO L226 Difference]: Without dead ends: 1639 [2024-11-08 14:17:46,356 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 263 GetRequests, 178 SyntacticMatches, 0 SemanticMatches, 85 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1837 ImplicationChecksByTransitivity, 14.1s TimeCoverageRelationStatistics Valid=1422, Invalid=6060, Unknown=0, NotChecked=0, Total=7482 [2024-11-08 14:17:46,356 INFO L432 NwaCegarLoop]: 57 mSDtfsCounter, 238 mSDsluCounter, 770 mSDsCounter, 0 mSdLazyCounter, 1353 mSolverCounterSat, 307 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 238 SdHoareTripleChecker+Valid, 827 SdHoareTripleChecker+Invalid, 1660 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 307 IncrementalHoareTripleChecker+Valid, 1353 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.6s IncrementalHoareTripleChecker+Time [2024-11-08 14:17:46,357 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [238 Valid, 827 Invalid, 1660 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [307 Valid, 1353 Invalid, 0 Unknown, 0 Unchecked, 4.6s Time] [2024-11-08 14:17:46,358 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1639 states. [2024-11-08 14:17:47,992 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1639 to 1500. [2024-11-08 14:17:47,994 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1500 states, 773 states have (on average 1.3014230271668823) internal successors, (1006), 777 states have internal predecessors, (1006), 685 states have call successors, (685), 41 states have call predecessors, (685), 41 states have return successors, (684), 681 states have call predecessors, (684), 684 states have call successors, (684) [2024-11-08 14:17:47,998 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1500 states to 1500 states and 2375 transitions. [2024-11-08 14:17:48,000 INFO L78 Accepts]: Start accepts. Automaton has 1500 states and 2375 transitions. Word has length 106 [2024-11-08 14:17:48,002 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:17:48,002 INFO L471 AbstractCegarLoop]: Abstraction has 1500 states and 2375 transitions. [2024-11-08 14:17:48,002 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 34 states, 34 states have (on average 2.088235294117647) internal successors, (71), 32 states have internal predecessors, (71), 11 states have call successors, (31), 3 states have call predecessors, (31), 3 states have return successors, (30), 11 states have call predecessors, (30), 11 states have call successors, (30) [2024-11-08 14:17:48,002 INFO L276 IsEmpty]: Start isEmpty. Operand 1500 states and 2375 transitions. [2024-11-08 14:17:48,004 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 110 [2024-11-08 14:17:48,004 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:17:48,004 INFO L215 NwaCegarLoop]: trace histogram [14, 13, 13, 5, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:17:48,018 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2024-11-08 14:17:48,208 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable21,19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:17:48,208 INFO L396 AbstractCegarLoop]: === Iteration 23 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:17:48,209 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:17:48,209 INFO L85 PathProgramCache]: Analyzing trace with hash 626542989, now seen corresponding path program 3 times [2024-11-08 14:17:48,209 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:17:48,209 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2036926672] [2024-11-08 14:17:48,209 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:17:48,209 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:17:48,224 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:17:48,225 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1227847769] [2024-11-08 14:17:48,225 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-08 14:17:48,225 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:17:48,225 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:17:48,227 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:17:48,227 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2024-11-08 14:17:48,270 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-08 14:17:48,270 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 14:17:48,271 INFO L255 TraceCheckSpWp]: Trace formula consists of 147 conjuncts, 55 conjuncts are in the unsatisfiable core [2024-11-08 14:17:48,273 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:17:48,786 INFO L134 CoverageAnalysis]: Checked inductivity of 397 backedges. 61 proven. 48 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2024-11-08 14:17:48,787 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:17:48,848 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:17:48,848 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2036926672] [2024-11-08 14:17:48,848 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:17:48,848 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1227847769] [2024-11-08 14:17:48,848 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1227847769] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:17:48,848 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-08 14:17:48,848 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2024-11-08 14:17:48,848 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1030075314] [2024-11-08 14:17:48,848 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-08 14:17:48,849 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-08 14:17:48,849 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:17:48,849 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-08 14:17:48,849 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=261, Unknown=0, NotChecked=0, Total=306 [2024-11-08 14:17:48,849 INFO L87 Difference]: Start difference. First operand 1500 states and 2375 transitions. Second operand has 15 states, 14 states have (on average 2.857142857142857) internal successors, (40), 13 states have internal predecessors, (40), 5 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-08 14:17:51,179 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:17:51,179 INFO L93 Difference]: Finished difference Result 1779 states and 2794 transitions. [2024-11-08 14:17:51,180 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-08 14:17:51,180 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 2.857142857142857) internal successors, (40), 13 states have internal predecessors, (40), 5 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) Word has length 109 [2024-11-08 14:17:51,180 INFO L84 Accepts]: Finished accepts. some prefix is accepted.