./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound10.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 3289d67d 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-scaling/egcd3-ll_valuebound10.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 776d32abf1ae3b62e7ad4a02cd7c02c0cc6433852a1fe73b7d30c6e216da832a --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.fs.icfgbuilder-eval-3289d67-m [2024-11-16 07:05:26,055 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-16 07:05:26,103 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-16 07:05:26,107 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-16 07:05:26,107 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-16 07:05:26,124 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-16 07:05:26,125 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-16 07:05:26,125 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-16 07:05:26,125 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-16 07:05:26,126 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-16 07:05:26,126 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-16 07:05:26,126 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-16 07:05:26,127 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-16 07:05:26,129 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-16 07:05:26,129 INFO L153 SettingsManager]: * Use SBE=true [2024-11-16 07:05:26,129 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-16 07:05:26,129 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-16 07:05:26,130 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-16 07:05:26,130 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-16 07:05:26,130 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-16 07:05:26,130 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-16 07:05:26,131 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-16 07:05:26,131 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-16 07:05:26,131 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-16 07:05:26,131 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-16 07:05:26,132 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-16 07:05:26,132 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-16 07:05:26,132 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-16 07:05:26,132 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2024-11-16 07:05:26,133 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-16 07:05:26,133 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-16 07:05:26,133 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-16 07:05:26,133 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-16 07:05:26,134 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-16 07:05:26,134 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-16 07:05:26,134 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-16 07:05:26,134 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-16 07:05:26,135 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-16 07:05:26,135 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-16 07:05:26,135 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-16 07:05:26,135 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-16 07:05:26,136 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-16 07:05:26,136 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 -> 776d32abf1ae3b62e7ad4a02cd7c02c0cc6433852a1fe73b7d30c6e216da832a [2024-11-16 07:05:26,334 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-16 07:05:26,351 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-16 07:05:26,354 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-16 07:05:26,355 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-16 07:05:26,355 INFO L274 PluginConnector]: CDTParser initialized [2024-11-16 07:05:26,356 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound10.c [2024-11-16 07:05:27,588 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-16 07:05:27,755 INFO L384 CDTParser]: Found 1 translation units. [2024-11-16 07:05:27,755 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound10.c [2024-11-16 07:05:27,761 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/1636c0cc1/828b2d369c3941f0b411c0a41ab18e70/FLAGe1d416105 [2024-11-16 07:05:28,140 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/1636c0cc1/828b2d369c3941f0b411c0a41ab18e70 [2024-11-16 07:05:28,142 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-16 07:05:28,144 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-16 07:05:28,146 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-16 07:05:28,146 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-16 07:05:28,150 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-16 07:05:28,151 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.11 07:05:28" (1/1) ... [2024-11-16 07:05:28,152 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@48ddfb93 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:05:28, skipping insertion in model container [2024-11-16 07:05:28,152 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.11 07:05:28" (1/1) ... [2024-11-16 07:05:28,169 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-16 07:05:28,304 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound10.c[490,503] [2024-11-16 07:05:28,327 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-16 07:05:28,339 INFO L200 MainTranslator]: Completed pre-run [2024-11-16 07:05:28,348 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound10.c[490,503] [2024-11-16 07:05:28,355 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-16 07:05:28,370 INFO L204 MainTranslator]: Completed translation [2024-11-16 07:05:28,371 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:05:28 WrapperNode [2024-11-16 07:05:28,371 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-16 07:05:28,372 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-16 07:05:28,372 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-16 07:05:28,372 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-16 07:05:28,377 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:05:28" (1/1) ... [2024-11-16 07:05:28,382 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:05:28" (1/1) ... [2024-11-16 07:05:28,398 INFO L138 Inliner]: procedures = 14, calls = 16, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 80 [2024-11-16 07:05:28,398 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-16 07:05:28,399 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-16 07:05:28,399 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-16 07:05:28,399 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-16 07:05:28,408 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:05:28" (1/1) ... [2024-11-16 07:05:28,408 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:05:28" (1/1) ... [2024-11-16 07:05:28,410 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:05:28" (1/1) ... [2024-11-16 07:05:28,419 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-16 07:05:28,420 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:05:28" (1/1) ... [2024-11-16 07:05:28,420 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:05:28" (1/1) ... [2024-11-16 07:05:28,422 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:05:28" (1/1) ... [2024-11-16 07:05:28,422 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:05:28" (1/1) ... [2024-11-16 07:05:28,425 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:05:28" (1/1) ... [2024-11-16 07:05:28,426 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:05:28" (1/1) ... [2024-11-16 07:05:28,427 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-16 07:05:28,429 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2024-11-16 07:05:28,430 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2024-11-16 07:05:28,430 INFO L274 PluginConnector]: IcfgBuilder initialized [2024-11-16 07:05:28,430 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:05:28" (1/1) ... [2024-11-16 07:05:28,435 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-16 07:05:28,445 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:05:28,459 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-16 07:05:28,461 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-16 07:05:28,502 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-16 07:05:28,502 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-16 07:05:28,503 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-16 07:05:28,503 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-16 07:05:28,503 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-16 07:05:28,503 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-16 07:05:28,504 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-16 07:05:28,504 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-16 07:05:28,563 INFO L256 CfgBuilder]: Building ICFG [2024-11-16 07:05:28,564 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-16 07:05:28,701 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-11-16 07:05:28,701 INFO L307 CfgBuilder]: Performing block encoding [2024-11-16 07:05:28,710 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-16 07:05:28,712 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-16 07:05:28,712 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.11 07:05:28 BoogieIcfgContainer [2024-11-16 07:05:28,713 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2024-11-16 07:05:28,714 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-16 07:05:28,715 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-16 07:05:28,718 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-16 07:05:28,718 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 16.11 07:05:28" (1/3) ... [2024-11-16 07:05:28,719 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@22104968 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.11 07:05:28, skipping insertion in model container [2024-11-16 07:05:28,719 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:05:28" (2/3) ... [2024-11-16 07:05:28,719 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@22104968 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.11 07:05:28, skipping insertion in model container [2024-11-16 07:05:28,720 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.11 07:05:28" (3/3) ... [2024-11-16 07:05:28,721 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd3-ll_valuebound10.c [2024-11-16 07:05:28,734 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-16 07:05:28,734 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-16 07:05:28,784 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-16 07:05:28,788 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;@11b8cfaf, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-16 07:05:28,789 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-16 07:05:28,791 INFO L276 IsEmpty]: Start isEmpty. Operand has 39 states, 26 states have (on average 1.4615384615384615) internal successors, (38), 27 states have internal predecessors, (38), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-16 07:05:28,797 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2024-11-16 07:05:28,798 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:05:28,798 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:05:28,800 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:05:28,804 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:05:28,805 INFO L85 PathProgramCache]: Analyzing trace with hash 1204067688, now seen corresponding path program 1 times [2024-11-16 07:05:28,811 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:05:28,812 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [838964957] [2024-11-16 07:05:28,812 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:28,812 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:05:28,882 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:28,916 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-16 07:05:28,918 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:28,924 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-16 07:05:28,926 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:28,929 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-16 07:05:28,931 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:28,933 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-16 07:05:28,936 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:28,941 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-16 07:05:28,943 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:05:28,943 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [838964957] [2024-11-16 07:05:28,944 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [838964957] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 07:05:28,944 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 07:05:28,944 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-16 07:05:28,945 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1297436090] [2024-11-16 07:05:28,946 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 07:05:28,949 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-16 07:05:28,949 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:05:28,966 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-16 07:05:28,966 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-16 07:05:28,968 INFO L87 Difference]: Start difference. First operand has 39 states, 26 states have (on average 1.4615384615384615) internal successors, (38), 27 states have internal predecessors, (38), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-16 07:05:28,984 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:05:28,984 INFO L93 Difference]: Finished difference Result 75 states and 117 transitions. [2024-11-16 07:05:28,985 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-16 07:05:28,986 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) Word has length 30 [2024-11-16 07:05:28,986 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:05:28,992 INFO L225 Difference]: With dead ends: 75 [2024-11-16 07:05:28,992 INFO L226 Difference]: Without dead ends: 35 [2024-11-16 07:05:28,995 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 14 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-16 07:05:28,999 INFO L432 NwaCegarLoop]: 48 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, 48 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-16 07:05:29,000 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 48 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-16 07:05:29,017 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2024-11-16 07:05:29,037 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 35. [2024-11-16 07:05:29,038 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 23 states have (on average 1.173913043478261) internal successors, (27), 24 states have internal predecessors, (27), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-16 07:05:29,040 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 44 transitions. [2024-11-16 07:05:29,042 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 44 transitions. Word has length 30 [2024-11-16 07:05:29,043 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:05:29,043 INFO L471 AbstractCegarLoop]: Abstraction has 35 states and 44 transitions. [2024-11-16 07:05:29,043 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-16 07:05:29,044 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 44 transitions. [2024-11-16 07:05:29,045 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2024-11-16 07:05:29,046 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:05:29,046 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:05:29,046 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-16 07:05:29,047 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:05:29,047 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:05:29,048 INFO L85 PathProgramCache]: Analyzing trace with hash -440055221, now seen corresponding path program 1 times [2024-11-16 07:05:29,048 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:05:29,048 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2117367946] [2024-11-16 07:05:29,048 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:29,049 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:05:29,084 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:29,267 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-16 07:05:29,269 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:29,275 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-16 07:05:29,277 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:29,280 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-16 07:05:29,302 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:29,305 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-16 07:05:29,309 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:29,352 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 9 proven. 0 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-16 07:05:29,353 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:05:29,353 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2117367946] [2024-11-16 07:05:29,353 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2117367946] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 07:05:29,353 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 07:05:29,353 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-16 07:05:29,354 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1474752736] [2024-11-16 07:05:29,354 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 07:05:29,355 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-16 07:05:29,355 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:05:29,355 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-16 07:05:29,355 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-16 07:05:29,356 INFO L87 Difference]: Start difference. First operand 35 states and 44 transitions. Second operand has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-16 07:05:29,448 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:05:29,448 INFO L93 Difference]: Finished difference Result 58 states and 73 transitions. [2024-11-16 07:05:29,449 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-16 07:05:29,449 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) Word has length 32 [2024-11-16 07:05:29,449 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:05:29,450 INFO L225 Difference]: With dead ends: 58 [2024-11-16 07:05:29,450 INFO L226 Difference]: Without dead ends: 50 [2024-11-16 07:05:29,450 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 9 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-16 07:05:29,451 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 25 mSDsluCounter, 102 mSDsCounter, 0 mSdLazyCounter, 60 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 136 SdHoareTripleChecker+Invalid, 60 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 60 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-16 07:05:29,451 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [33 Valid, 136 Invalid, 60 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 60 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-16 07:05:29,453 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2024-11-16 07:05:29,461 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 38. [2024-11-16 07:05:29,462 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 38 states, 26 states have (on average 1.1538461538461537) internal successors, (30), 27 states have internal predecessors, (30), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-16 07:05:29,464 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 47 transitions. [2024-11-16 07:05:29,465 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 47 transitions. Word has length 32 [2024-11-16 07:05:29,466 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:05:29,466 INFO L471 AbstractCegarLoop]: Abstraction has 38 states and 47 transitions. [2024-11-16 07:05:29,466 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-16 07:05:29,466 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 47 transitions. [2024-11-16 07:05:29,467 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2024-11-16 07:05:29,467 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:05:29,467 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 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-16 07:05:29,468 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-16 07:05:29,468 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:05:29,468 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:05:29,468 INFO L85 PathProgramCache]: Analyzing trace with hash -1503367536, now seen corresponding path program 1 times [2024-11-16 07:05:29,468 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:05:29,469 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [48513540] [2024-11-16 07:05:29,469 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:29,469 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:05:29,485 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:05:29,487 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1784916055] [2024-11-16 07:05:29,487 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:29,487 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:05:29,487 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:05:29,489 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-16 07:05:29,490 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-16 07:05:29,539 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:29,541 INFO L255 TraceCheckSpWp]: Trace formula consists of 99 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-16 07:05:29,546 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:05:29,682 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-16 07:05:29,683 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-16 07:05:29,684 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:05:29,684 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [48513540] [2024-11-16 07:05:29,685 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:05:29,685 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1784916055] [2024-11-16 07:05:29,686 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1784916055] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 07:05:29,686 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 07:05:29,687 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-16 07:05:29,687 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1399622026] [2024-11-16 07:05:29,687 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 07:05:29,689 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-16 07:05:29,689 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:05:29,690 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-16 07:05:29,690 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-16 07:05:29,690 INFO L87 Difference]: Start difference. First operand 38 states and 47 transitions. Second operand has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-16 07:05:29,733 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:05:29,733 INFO L93 Difference]: Finished difference Result 57 states and 71 transitions. [2024-11-16 07:05:29,733 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-16 07:05:29,734 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 37 [2024-11-16 07:05:29,734 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:05:29,736 INFO L225 Difference]: With dead ends: 57 [2024-11-16 07:05:29,737 INFO L226 Difference]: Without dead ends: 54 [2024-11-16 07:05:29,738 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-16 07:05:29,739 INFO L432 NwaCegarLoop]: 39 mSDtfsCounter, 7 mSDsluCounter, 111 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 150 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-16 07:05:29,740 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 150 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-16 07:05:29,741 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2024-11-16 07:05:29,752 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 53. [2024-11-16 07:05:29,753 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 53 states, 36 states have (on average 1.1666666666666667) internal successors, (42), 37 states have internal predecessors, (42), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-16 07:05:29,754 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 67 transitions. [2024-11-16 07:05:29,754 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 67 transitions. Word has length 37 [2024-11-16 07:05:29,754 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:05:29,754 INFO L471 AbstractCegarLoop]: Abstraction has 53 states and 67 transitions. [2024-11-16 07:05:29,754 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-16 07:05:29,755 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 67 transitions. [2024-11-16 07:05:29,755 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2024-11-16 07:05:29,755 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:05:29,756 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 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] [2024-11-16 07:05:29,767 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-16 07:05:29,959 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-16 07:05:29,959 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:05:29,960 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:05:29,960 INFO L85 PathProgramCache]: Analyzing trace with hash 383673201, now seen corresponding path program 1 times [2024-11-16 07:05:29,960 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:05:29,960 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1172464981] [2024-11-16 07:05:29,960 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:29,960 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:05:29,975 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:30,103 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-16 07:05:30,104 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:30,107 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-16 07:05:30,111 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:30,112 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-16 07:05:30,113 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:30,136 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-16 07:05:30,137 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:30,141 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 6 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-16 07:05:30,142 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:05:30,142 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1172464981] [2024-11-16 07:05:30,142 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1172464981] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 07:05:30,142 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1180528180] [2024-11-16 07:05:30,142 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:30,144 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:05:30,144 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:05:30,146 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-16 07:05:30,148 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-16 07:05:30,189 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:30,190 INFO L255 TraceCheckSpWp]: Trace formula consists of 109 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-16 07:05:30,191 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:05:30,232 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 6 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-16 07:05:30,232 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:05:30,311 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 6 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-16 07:05:30,312 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1180528180] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 07:05:30,312 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-16 07:05:30,312 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 12 [2024-11-16 07:05:30,313 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [713608827] [2024-11-16 07:05:30,314 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-16 07:05:30,315 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-16 07:05:30,315 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:05:30,315 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-16 07:05:30,315 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=103, Unknown=0, NotChecked=0, Total=132 [2024-11-16 07:05:30,316 INFO L87 Difference]: Start difference. First operand 53 states and 67 transitions. Second operand has 12 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 11 states have internal predecessors, (37), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-16 07:05:30,556 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:05:30,558 INFO L93 Difference]: Finished difference Result 118 states and 158 transitions. [2024-11-16 07:05:30,558 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-16 07:05:30,558 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 11 states have internal predecessors, (37), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 39 [2024-11-16 07:05:30,559 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:05:30,559 INFO L225 Difference]: With dead ends: 118 [2024-11-16 07:05:30,559 INFO L226 Difference]: Without dead ends: 110 [2024-11-16 07:05:30,560 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 94 GetRequests, 77 SyntacticMatches, 4 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 44 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=54, Invalid=156, Unknown=0, NotChecked=0, Total=210 [2024-11-16 07:05:30,560 INFO L432 NwaCegarLoop]: 47 mSDtfsCounter, 66 mSDsluCounter, 337 mSDsCounter, 0 mSdLazyCounter, 167 mSolverCounterSat, 21 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 74 SdHoareTripleChecker+Valid, 384 SdHoareTripleChecker+Invalid, 188 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 21 IncrementalHoareTripleChecker+Valid, 167 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-16 07:05:30,561 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [74 Valid, 384 Invalid, 188 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [21 Valid, 167 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-16 07:05:30,561 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 110 states. [2024-11-16 07:05:30,576 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 110 to 81. [2024-11-16 07:05:30,577 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 81 states, 60 states have (on average 1.2) internal successors, (72), 61 states have internal predecessors, (72), 17 states have call successors, (17), 3 states have call predecessors, (17), 3 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2024-11-16 07:05:30,580 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 81 states to 81 states and 105 transitions. [2024-11-16 07:05:30,581 INFO L78 Accepts]: Start accepts. Automaton has 81 states and 105 transitions. Word has length 39 [2024-11-16 07:05:30,581 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:05:30,581 INFO L471 AbstractCegarLoop]: Abstraction has 81 states and 105 transitions. [2024-11-16 07:05:30,581 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 11 states have internal predecessors, (37), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-16 07:05:30,582 INFO L276 IsEmpty]: Start isEmpty. Operand 81 states and 105 transitions. [2024-11-16 07:05:30,582 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2024-11-16 07:05:30,583 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:05:30,583 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 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, 1, 1] [2024-11-16 07:05:30,595 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-16 07:05:30,785 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-16 07:05:30,786 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:05:30,786 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:05:30,786 INFO L85 PathProgramCache]: Analyzing trace with hash -1151148547, now seen corresponding path program 1 times [2024-11-16 07:05:30,786 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:05:30,787 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [821260242] [2024-11-16 07:05:30,787 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:30,787 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:05:30,797 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:05:30,798 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [48187628] [2024-11-16 07:05:30,798 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:30,799 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:05:30,799 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:05:30,800 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-16 07:05:30,801 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-16 07:05:30,849 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:30,852 INFO L255 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-16 07:05:30,854 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:05:30,924 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-16 07:05:30,924 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-16 07:05:30,924 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:05:30,925 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [821260242] [2024-11-16 07:05:30,925 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:05:30,925 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [48187628] [2024-11-16 07:05:30,925 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [48187628] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 07:05:30,925 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 07:05:30,925 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-16 07:05:30,925 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [488910829] [2024-11-16 07:05:30,925 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 07:05:30,926 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-16 07:05:30,926 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:05:30,926 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-16 07:05:30,926 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-16 07:05:30,926 INFO L87 Difference]: Start difference. First operand 81 states and 105 transitions. Second operand has 5 states, 5 states have (on average 4.4) internal successors, (22), 4 states have internal predecessors, (22), 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-16 07:05:30,979 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:05:30,981 INFO L93 Difference]: Finished difference Result 90 states and 113 transitions. [2024-11-16 07:05:30,982 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-16 07:05:30,982 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.4) internal successors, (22), 4 states have internal predecessors, (22), 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 42 [2024-11-16 07:05:30,982 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:05:30,983 INFO L225 Difference]: With dead ends: 90 [2024-11-16 07:05:30,983 INFO L226 Difference]: Without dead ends: 87 [2024-11-16 07:05:30,983 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 38 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-16 07:05:30,984 INFO L432 NwaCegarLoop]: 40 mSDtfsCounter, 7 mSDsluCounter, 107 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 147 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-16 07:05:30,984 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 147 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-16 07:05:30,985 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 87 states. [2024-11-16 07:05:30,993 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 87 to 85. [2024-11-16 07:05:30,993 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 85 states, 63 states have (on average 1.1904761904761905) internal successors, (75), 64 states have internal predecessors, (75), 17 states have call successors, (17), 4 states have call predecessors, (17), 4 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2024-11-16 07:05:30,995 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 85 states to 85 states and 108 transitions. [2024-11-16 07:05:30,995 INFO L78 Accepts]: Start accepts. Automaton has 85 states and 108 transitions. Word has length 42 [2024-11-16 07:05:30,995 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:05:30,996 INFO L471 AbstractCegarLoop]: Abstraction has 85 states and 108 transitions. [2024-11-16 07:05:30,998 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.4) internal successors, (22), 4 states have internal predecessors, (22), 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-16 07:05:30,998 INFO L276 IsEmpty]: Start isEmpty. Operand 85 states and 108 transitions. [2024-11-16 07:05:30,998 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2024-11-16 07:05:30,999 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:05:30,999 INFO L215 NwaCegarLoop]: trace histogram [4, 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] [2024-11-16 07:05:31,014 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-16 07:05:31,202 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-16 07:05:31,203 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:05:31,203 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:05:31,203 INFO L85 PathProgramCache]: Analyzing trace with hash 652942634, now seen corresponding path program 1 times [2024-11-16 07:05:31,203 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:05:31,203 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [96871125] [2024-11-16 07:05:31,203 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:31,203 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:05:31,218 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:05:31,219 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1556364531] [2024-11-16 07:05:31,219 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:31,219 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:05:31,219 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:05:31,223 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-16 07:05:31,224 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-16 07:05:31,262 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:31,264 INFO L255 TraceCheckSpWp]: Trace formula consists of 121 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-11-16 07:05:31,266 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:05:31,375 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-16 07:05:31,375 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:05:31,540 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-16 07:05:31,540 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:05:31,540 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [96871125] [2024-11-16 07:05:31,541 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:05:31,541 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1556364531] [2024-11-16 07:05:31,541 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1556364531] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 07:05:31,541 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-16 07:05:31,542 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2024-11-16 07:05:31,542 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [673966471] [2024-11-16 07:05:31,542 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-16 07:05:31,542 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-16 07:05:31,543 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:05:31,544 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-16 07:05:31,544 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2024-11-16 07:05:31,544 INFO L87 Difference]: Start difference. First operand 85 states and 108 transitions. Second operand has 10 states, 10 states have (on average 4.4) internal successors, (44), 8 states have internal predecessors, (44), 3 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-16 07:05:31,748 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:05:31,748 INFO L93 Difference]: Finished difference Result 129 states and 165 transitions. [2024-11-16 07:05:31,748 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-16 07:05:31,749 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 4.4) internal successors, (44), 8 states have internal predecessors, (44), 3 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 44 [2024-11-16 07:05:31,749 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:05:31,749 INFO L225 Difference]: With dead ends: 129 [2024-11-16 07:05:31,750 INFO L226 Difference]: Without dead ends: 126 [2024-11-16 07:05:31,750 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 87 GetRequests, 78 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2024-11-16 07:05:31,750 INFO L432 NwaCegarLoop]: 58 mSDtfsCounter, 14 mSDsluCounter, 299 mSDsCounter, 0 mSdLazyCounter, 108 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 357 SdHoareTripleChecker+Invalid, 109 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 108 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-16 07:05:31,751 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 357 Invalid, 109 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 108 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-16 07:05:31,751 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 126 states. [2024-11-16 07:05:31,766 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 126 to 122. [2024-11-16 07:05:31,766 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 122 states, 91 states have (on average 1.1978021978021978) internal successors, (109), 92 states have internal predecessors, (109), 25 states have call successors, (25), 5 states have call predecessors, (25), 5 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) [2024-11-16 07:05:31,769 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 122 states to 122 states and 158 transitions. [2024-11-16 07:05:31,770 INFO L78 Accepts]: Start accepts. Automaton has 122 states and 158 transitions. Word has length 44 [2024-11-16 07:05:31,770 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:05:31,770 INFO L471 AbstractCegarLoop]: Abstraction has 122 states and 158 transitions. [2024-11-16 07:05:31,770 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 4.4) internal successors, (44), 8 states have internal predecessors, (44), 3 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-16 07:05:31,770 INFO L276 IsEmpty]: Start isEmpty. Operand 122 states and 158 transitions. [2024-11-16 07:05:31,771 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2024-11-16 07:05:31,771 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:05:31,771 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 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, 1, 1] [2024-11-16 07:05:31,784 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-16 07:05:31,971 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-16 07:05:31,971 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:05:31,972 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:05:31,972 INFO L85 PathProgramCache]: Analyzing trace with hash 898378352, now seen corresponding path program 1 times [2024-11-16 07:05:31,972 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:05:31,972 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [828596562] [2024-11-16 07:05:31,972 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:31,972 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:05:31,982 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:05:31,984 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1756046924] [2024-11-16 07:05:31,984 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:31,985 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:05:31,985 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:05:31,986 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-16 07:05:31,987 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-16 07:05:32,023 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:32,024 INFO L255 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-16 07:05:32,025 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:05:32,063 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-16 07:05:32,064 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-16 07:05:32,064 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:05:32,064 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [828596562] [2024-11-16 07:05:32,064 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:05:32,064 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1756046924] [2024-11-16 07:05:32,064 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1756046924] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 07:05:32,064 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 07:05:32,064 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-16 07:05:32,064 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [870884639] [2024-11-16 07:05:32,065 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 07:05:32,065 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-16 07:05:32,065 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:05:32,065 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-16 07:05:32,065 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-16 07:05:32,066 INFO L87 Difference]: Start difference. First operand 122 states and 158 transitions. Second operand has 5 states, 5 states have (on average 4.4) internal successors, (22), 4 states have internal predecessors, (22), 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-16 07:05:32,118 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:05:32,118 INFO L93 Difference]: Finished difference Result 176 states and 238 transitions. [2024-11-16 07:05:32,119 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-16 07:05:32,119 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.4) internal successors, (22), 4 states have internal predecessors, (22), 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 47 [2024-11-16 07:05:32,121 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:05:32,123 INFO L225 Difference]: With dead ends: 176 [2024-11-16 07:05:32,123 INFO L226 Difference]: Without dead ends: 173 [2024-11-16 07:05:32,123 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 43 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-16 07:05:32,123 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 6 mSDsluCounter, 102 mSDsCounter, 0 mSdLazyCounter, 43 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 140 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.0s IncrementalHoareTripleChecker+Time [2024-11-16 07:05:32,124 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 140 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 43 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-16 07:05:32,126 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 173 states. [2024-11-16 07:05:32,153 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 173 to 167. [2024-11-16 07:05:32,156 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 167 states, 115 states have (on average 1.2173913043478262) internal successors, (140), 116 states have internal predecessors, (140), 45 states have call successors, (45), 6 states have call predecessors, (45), 6 states have return successors, (44), 44 states have call predecessors, (44), 44 states have call successors, (44) [2024-11-16 07:05:32,157 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 167 states to 167 states and 229 transitions. [2024-11-16 07:05:32,158 INFO L78 Accepts]: Start accepts. Automaton has 167 states and 229 transitions. Word has length 47 [2024-11-16 07:05:32,158 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:05:32,159 INFO L471 AbstractCegarLoop]: Abstraction has 167 states and 229 transitions. [2024-11-16 07:05:32,160 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.4) internal successors, (22), 4 states have internal predecessors, (22), 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-16 07:05:32,160 INFO L276 IsEmpty]: Start isEmpty. Operand 167 states and 229 transitions. [2024-11-16 07:05:32,160 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2024-11-16 07:05:32,160 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:05:32,160 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 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] [2024-11-16 07:05:32,176 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-16 07:05:32,361 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-16 07:05:32,361 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:05:32,362 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:05:32,362 INFO L85 PathProgramCache]: Analyzing trace with hash -1868349533, now seen corresponding path program 1 times [2024-11-16 07:05:32,362 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:05:32,362 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1798721430] [2024-11-16 07:05:32,362 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:32,362 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:05:32,372 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:05:32,372 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1454776698] [2024-11-16 07:05:32,372 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:32,373 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:05:32,373 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:05:32,374 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-16 07:05:32,375 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-16 07:05:32,415 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:32,416 INFO L255 TraceCheckSpWp]: Trace formula consists of 130 conjuncts, 29 conjuncts are in the unsatisfiable core [2024-11-16 07:05:32,417 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:05:32,571 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 1 proven. 7 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-16 07:05:32,571 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:05:32,634 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:05:32,634 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1798721430] [2024-11-16 07:05:32,634 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:05:32,634 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1454776698] [2024-11-16 07:05:32,634 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1454776698] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 07:05:32,634 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-16 07:05:32,634 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2024-11-16 07:05:32,634 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [16399195] [2024-11-16 07:05:32,635 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-16 07:05:32,635 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-16 07:05:32,635 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:05:32,635 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-16 07:05:32,635 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=106, Unknown=0, NotChecked=0, Total=132 [2024-11-16 07:05:32,636 INFO L87 Difference]: Start difference. First operand 167 states and 229 transitions. Second operand has 9 states, 9 states have (on average 3.2222222222222223) internal successors, (29), 8 states have internal predecessors, (29), 2 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-16 07:05:32,784 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:05:32,784 INFO L93 Difference]: Finished difference Result 181 states and 241 transitions. [2024-11-16 07:05:32,785 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-16 07:05:32,785 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 3.2222222222222223) internal successors, (29), 8 states have internal predecessors, (29), 2 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 49 [2024-11-16 07:05:32,786 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:05:32,787 INFO L225 Difference]: With dead ends: 181 [2024-11-16 07:05:32,787 INFO L226 Difference]: Without dead ends: 178 [2024-11-16 07:05:32,787 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 56 GetRequests, 44 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=37, Invalid=145, Unknown=0, NotChecked=0, Total=182 [2024-11-16 07:05:32,788 INFO L432 NwaCegarLoop]: 43 mSDtfsCounter, 32 mSDsluCounter, 215 mSDsCounter, 0 mSdLazyCounter, 160 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 258 SdHoareTripleChecker+Invalid, 174 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 160 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-16 07:05:32,788 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [39 Valid, 258 Invalid, 174 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 160 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-16 07:05:32,788 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 178 states. [2024-11-16 07:05:32,808 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 178 to 175. [2024-11-16 07:05:32,809 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 175 states, 121 states have (on average 1.2066115702479339) internal successors, (146), 122 states have internal predecessors, (146), 45 states have call successors, (45), 8 states have call predecessors, (45), 8 states have return successors, (44), 44 states have call predecessors, (44), 44 states have call successors, (44) [2024-11-16 07:05:32,810 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 175 states to 175 states and 235 transitions. [2024-11-16 07:05:32,811 INFO L78 Accepts]: Start accepts. Automaton has 175 states and 235 transitions. Word has length 49 [2024-11-16 07:05:32,811 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:05:32,812 INFO L471 AbstractCegarLoop]: Abstraction has 175 states and 235 transitions. [2024-11-16 07:05:32,812 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 3.2222222222222223) internal successors, (29), 8 states have internal predecessors, (29), 2 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-16 07:05:32,812 INFO L276 IsEmpty]: Start isEmpty. Operand 175 states and 235 transitions. [2024-11-16 07:05:32,813 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2024-11-16 07:05:32,814 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:05:32,814 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 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, 1, 1, 1, 1] [2024-11-16 07:05:32,830 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-11-16 07:05:33,018 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-16 07:05:33,019 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:05:33,019 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:05:33,019 INFO L85 PathProgramCache]: Analyzing trace with hash 503958941, now seen corresponding path program 1 times [2024-11-16 07:05:33,019 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:05:33,019 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [740990044] [2024-11-16 07:05:33,019 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:33,019 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:05:33,027 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:05:33,028 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1775852390] [2024-11-16 07:05:33,028 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:33,028 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:05:33,028 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:05:33,029 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-16 07:05:33,030 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-16 07:05:33,065 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:33,066 INFO L255 TraceCheckSpWp]: Trace formula consists of 126 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-16 07:05:33,067 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:05:33,102 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-11-16 07:05:33,102 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-16 07:05:33,102 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:05:33,103 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [740990044] [2024-11-16 07:05:33,103 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:05:33,103 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1775852390] [2024-11-16 07:05:33,103 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1775852390] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 07:05:33,103 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 07:05:33,103 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-16 07:05:33,103 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2077022380] [2024-11-16 07:05:33,103 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 07:05:33,103 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-16 07:05:33,104 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:05:33,104 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-16 07:05:33,104 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-16 07:05:33,104 INFO L87 Difference]: Start difference. First operand 175 states and 235 transitions. Second operand has 5 states, 5 states have (on average 4.4) internal successors, (22), 4 states have internal predecessors, (22), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-16 07:05:33,166 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:05:33,166 INFO L93 Difference]: Finished difference Result 257 states and 366 transitions. [2024-11-16 07:05:33,167 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-16 07:05:33,167 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.4) internal successors, (22), 4 states have internal predecessors, (22), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 52 [2024-11-16 07:05:33,167 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:05:33,168 INFO L225 Difference]: With dead ends: 257 [2024-11-16 07:05:33,168 INFO L226 Difference]: Without dead ends: 254 [2024-11-16 07:05:33,169 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 52 GetRequests, 48 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-16 07:05:33,169 INFO L432 NwaCegarLoop]: 41 mSDtfsCounter, 4 mSDsluCounter, 107 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 148 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-16 07:05:33,169 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 148 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-16 07:05:33,170 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 254 states. [2024-11-16 07:05:33,196 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 254 to 239. [2024-11-16 07:05:33,198 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 239 states, 144 states have (on average 1.1736111111111112) internal successors, (169), 155 states have internal predecessors, (169), 85 states have call successors, (85), 9 states have call predecessors, (85), 9 states have return successors, (84), 74 states have call predecessors, (84), 84 states have call successors, (84) [2024-11-16 07:05:33,199 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 239 states to 239 states and 338 transitions. [2024-11-16 07:05:33,199 INFO L78 Accepts]: Start accepts. Automaton has 239 states and 338 transitions. Word has length 52 [2024-11-16 07:05:33,200 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:05:33,200 INFO L471 AbstractCegarLoop]: Abstraction has 239 states and 338 transitions. [2024-11-16 07:05:33,200 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.4) internal successors, (22), 4 states have internal predecessors, (22), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-16 07:05:33,200 INFO L276 IsEmpty]: Start isEmpty. Operand 239 states and 338 transitions. [2024-11-16 07:05:33,201 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2024-11-16 07:05:33,201 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:05:33,201 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:05:33,213 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-16 07:05:33,401 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:05:33,401 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:05:33,402 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:05:33,402 INFO L85 PathProgramCache]: Analyzing trace with hash -1382437552, now seen corresponding path program 2 times [2024-11-16 07:05:33,402 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:05:33,402 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1018041181] [2024-11-16 07:05:33,402 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:33,402 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:05:33,408 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:33,447 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-16 07:05:33,448 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:33,451 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-16 07:05:33,453 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:33,454 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-16 07:05:33,455 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:33,456 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-16 07:05:33,457 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:33,459 INFO L134 CoverageAnalysis]: Checked inductivity of 43 backedges. 19 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-16 07:05:33,459 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:05:33,459 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1018041181] [2024-11-16 07:05:33,459 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1018041181] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 07:05:33,459 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 07:05:33,459 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-16 07:05:33,459 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [485734545] [2024-11-16 07:05:33,459 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 07:05:33,460 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-16 07:05:33,462 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:05:33,463 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-16 07:05:33,463 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-16 07:05:33,463 INFO L87 Difference]: Start difference. First operand 239 states and 338 transitions. Second operand has 5 states, 5 states have (on average 6.6) internal successors, (33), 5 states have internal predecessors, (33), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-16 07:05:33,539 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:05:33,540 INFO L93 Difference]: Finished difference Result 302 states and 421 transitions. [2024-11-16 07:05:33,540 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-16 07:05:33,540 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 6.6) internal successors, (33), 5 states have internal predecessors, (33), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 51 [2024-11-16 07:05:33,540 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:05:33,543 INFO L225 Difference]: With dead ends: 302 [2024-11-16 07:05:33,543 INFO L226 Difference]: Without dead ends: 205 [2024-11-16 07:05:33,544 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 11 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-16 07:05:33,544 INFO L432 NwaCegarLoop]: 56 mSDtfsCounter, 23 mSDsluCounter, 129 mSDsCounter, 0 mSdLazyCounter, 54 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 185 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-16 07:05:33,544 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 185 Invalid, 62 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 54 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-16 07:05:33,545 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 205 states. [2024-11-16 07:05:33,561 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 205 to 195. [2024-11-16 07:05:33,562 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 195 states, 116 states have (on average 1.1379310344827587) internal successors, (132), 125 states have internal predecessors, (132), 69 states have call successors, (69), 9 states have call predecessors, (69), 9 states have return successors, (68), 60 states have call predecessors, (68), 68 states have call successors, (68) [2024-11-16 07:05:33,563 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 195 states to 195 states and 269 transitions. [2024-11-16 07:05:33,563 INFO L78 Accepts]: Start accepts. Automaton has 195 states and 269 transitions. Word has length 51 [2024-11-16 07:05:33,563 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:05:33,563 INFO L471 AbstractCegarLoop]: Abstraction has 195 states and 269 transitions. [2024-11-16 07:05:33,563 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 6.6) internal successors, (33), 5 states have internal predecessors, (33), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-16 07:05:33,564 INFO L276 IsEmpty]: Start isEmpty. Operand 195 states and 269 transitions. [2024-11-16 07:05:33,564 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 67 [2024-11-16 07:05:33,564 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:05:33,564 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 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, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:05:33,565 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9 [2024-11-16 07:05:33,565 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:05:33,565 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:05:33,565 INFO L85 PathProgramCache]: Analyzing trace with hash 538614248, now seen corresponding path program 1 times [2024-11-16 07:05:33,565 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:05:33,565 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [213087078] [2024-11-16 07:05:33,565 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:33,565 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:05:33,578 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:05:33,581 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1555964921] [2024-11-16 07:05:33,581 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:33,582 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:05:33,582 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:05:33,583 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-16 07:05:33,584 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-16 07:05:33,628 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:33,629 INFO L255 TraceCheckSpWp]: Trace formula consists of 159 conjuncts, 51 conjuncts are in the unsatisfiable core [2024-11-16 07:05:33,631 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:05:34,182 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 14 proven. 9 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-16 07:05:34,182 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:05:35,356 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 8 proven. 6 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-11-16 07:05:35,356 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:05:35,356 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [213087078] [2024-11-16 07:05:35,356 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:05:35,356 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1555964921] [2024-11-16 07:05:35,356 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1555964921] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 07:05:35,356 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-16 07:05:35,356 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 23 [2024-11-16 07:05:35,356 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1582521364] [2024-11-16 07:05:35,356 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-16 07:05:35,357 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-11-16 07:05:35,357 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:05:35,357 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-16 07:05:35,357 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=77, Invalid=429, Unknown=0, NotChecked=0, Total=506 [2024-11-16 07:05:35,357 INFO L87 Difference]: Start difference. First operand 195 states and 269 transitions. Second operand has 23 states, 21 states have (on average 2.5714285714285716) internal successors, (54), 20 states have internal predecessors, (54), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2024-11-16 07:05:38,436 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:05:38,436 INFO L93 Difference]: Finished difference Result 526 states and 746 transitions. [2024-11-16 07:05:38,437 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2024-11-16 07:05:38,437 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 21 states have (on average 2.5714285714285716) internal successors, (54), 20 states have internal predecessors, (54), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) Word has length 66 [2024-11-16 07:05:38,437 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:05:38,441 INFO L225 Difference]: With dead ends: 526 [2024-11-16 07:05:38,441 INFO L226 Difference]: Without dead ends: 405 [2024-11-16 07:05:38,443 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 153 GetRequests, 109 SyntacticMatches, 0 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 429 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=398, Invalid=1672, Unknown=0, NotChecked=0, Total=2070 [2024-11-16 07:05:38,444 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 226 mSDsluCounter, 449 mSDsCounter, 0 mSdLazyCounter, 571 mSolverCounterSat, 153 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 234 SdHoareTripleChecker+Valid, 487 SdHoareTripleChecker+Invalid, 724 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 153 IncrementalHoareTripleChecker+Valid, 571 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.6s IncrementalHoareTripleChecker+Time [2024-11-16 07:05:38,444 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [234 Valid, 487 Invalid, 724 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [153 Valid, 571 Invalid, 0 Unknown, 0 Unchecked, 1.6s Time] [2024-11-16 07:05:38,444 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 405 states. [2024-11-16 07:05:38,511 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 405 to 305. [2024-11-16 07:05:38,511 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 305 states, 199 states have (on average 1.1557788944723617) internal successors, (230), 206 states have internal predecessors, (230), 93 states have call successors, (93), 12 states have call predecessors, (93), 12 states have return successors, (92), 86 states have call predecessors, (92), 92 states have call successors, (92) [2024-11-16 07:05:38,513 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 305 states to 305 states and 415 transitions. [2024-11-16 07:05:38,513 INFO L78 Accepts]: Start accepts. Automaton has 305 states and 415 transitions. Word has length 66 [2024-11-16 07:05:38,513 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:05:38,514 INFO L471 AbstractCegarLoop]: Abstraction has 305 states and 415 transitions. [2024-11-16 07:05:38,514 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 21 states have (on average 2.5714285714285716) internal successors, (54), 20 states have internal predecessors, (54), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2024-11-16 07:05:38,514 INFO L276 IsEmpty]: Start isEmpty. Operand 305 states and 415 transitions. [2024-11-16 07:05:38,514 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2024-11-16 07:05:38,515 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:05:38,515 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 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, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:05:38,526 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2024-11-16 07:05:38,718 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-16 07:05:38,719 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:05:38,719 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:05:38,719 INFO L85 PathProgramCache]: Analyzing trace with hash -308189961, now seen corresponding path program 1 times [2024-11-16 07:05:38,719 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:05:38,719 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1799156061] [2024-11-16 07:05:38,719 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:38,719 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:05:38,731 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:05:38,732 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1314843810] [2024-11-16 07:05:38,732 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:38,732 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:05:38,732 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:05:38,735 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-16 07:05:38,736 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-16 07:05:38,773 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:38,774 INFO L255 TraceCheckSpWp]: Trace formula consists of 169 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-11-16 07:05:38,775 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:05:38,827 INFO L134 CoverageAnalysis]: Checked inductivity of 128 backedges. 14 proven. 6 refuted. 0 times theorem prover too weak. 108 trivial. 0 not checked. [2024-11-16 07:05:38,828 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:05:38,888 INFO L134 CoverageAnalysis]: Checked inductivity of 128 backedges. 14 proven. 0 refuted. 0 times theorem prover too weak. 114 trivial. 0 not checked. [2024-11-16 07:05:38,889 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:05:38,889 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1799156061] [2024-11-16 07:05:38,889 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:05:38,889 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1314843810] [2024-11-16 07:05:38,889 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1314843810] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-16 07:05:38,889 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-16 07:05:38,889 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2024-11-16 07:05:38,889 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1412420400] [2024-11-16 07:05:38,889 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 07:05:38,889 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-16 07:05:38,889 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:05:38,890 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-16 07:05:38,890 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-16 07:05:38,890 INFO L87 Difference]: Start difference. First operand 305 states and 415 transitions. Second operand has 5 states, 5 states have (on average 4.6) internal successors, (23), 4 states have internal predecessors, (23), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-11-16 07:05:38,982 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:05:38,982 INFO L93 Difference]: Finished difference Result 312 states and 421 transitions. [2024-11-16 07:05:38,982 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-16 07:05:38,983 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.6) internal successors, (23), 4 states have internal predecessors, (23), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 75 [2024-11-16 07:05:38,983 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:05:38,984 INFO L225 Difference]: With dead ends: 312 [2024-11-16 07:05:38,985 INFO L226 Difference]: Without dead ends: 309 [2024-11-16 07:05:38,985 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 149 GetRequests, 141 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-16 07:05:38,985 INFO L432 NwaCegarLoop]: 41 mSDtfsCounter, 4 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 142 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-16 07:05:38,986 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 142 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-16 07:05:38,987 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 309 states. [2024-11-16 07:05:39,048 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 309 to 309. [2024-11-16 07:05:39,049 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 309 states, 202 states have (on average 1.1534653465346534) internal successors, (233), 209 states have internal predecessors, (233), 93 states have call successors, (93), 13 states have call predecessors, (93), 13 states have return successors, (92), 86 states have call predecessors, (92), 92 states have call successors, (92) [2024-11-16 07:05:39,050 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 309 states to 309 states and 418 transitions. [2024-11-16 07:05:39,051 INFO L78 Accepts]: Start accepts. Automaton has 309 states and 418 transitions. Word has length 75 [2024-11-16 07:05:39,051 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:05:39,051 INFO L471 AbstractCegarLoop]: Abstraction has 309 states and 418 transitions. [2024-11-16 07:05:39,051 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.6) internal successors, (23), 4 states have internal predecessors, (23), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-11-16 07:05:39,051 INFO L276 IsEmpty]: Start isEmpty. Operand 309 states and 418 transitions. [2024-11-16 07:05:39,052 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2024-11-16 07:05:39,052 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:05:39,052 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 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] [2024-11-16 07:05:39,064 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2024-11-16 07:05:39,252 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-16 07:05:39,253 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:05:39,253 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:05:39,253 INFO L85 PathProgramCache]: Analyzing trace with hash -2085625555, now seen corresponding path program 1 times [2024-11-16 07:05:39,253 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:05:39,254 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1288453657] [2024-11-16 07:05:39,254 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:39,254 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:05:39,266 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:05:39,267 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1255326966] [2024-11-16 07:05:39,267 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:39,267 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:05:39,267 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:05:39,268 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-16 07:05:39,271 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-16 07:05:39,311 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:39,312 INFO L255 TraceCheckSpWp]: Trace formula consists of 193 conjuncts, 49 conjuncts are in the unsatisfiable core [2024-11-16 07:05:39,314 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:05:39,723 INFO L134 CoverageAnalysis]: Checked inductivity of 87 backedges. 16 proven. 41 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2024-11-16 07:05:39,723 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:05:39,878 INFO L134 CoverageAnalysis]: Checked inductivity of 87 backedges. 32 proven. 10 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-16 07:05:39,878 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:05:39,879 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1288453657] [2024-11-16 07:05:39,879 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:05:39,879 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1255326966] [2024-11-16 07:05:39,879 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1255326966] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 07:05:39,879 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-16 07:05:39,879 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 8] total 22 [2024-11-16 07:05:39,879 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1444402681] [2024-11-16 07:05:39,879 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-16 07:05:39,879 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-11-16 07:05:39,879 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:05:39,880 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-16 07:05:39,880 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=395, Unknown=0, NotChecked=0, Total=462 [2024-11-16 07:05:39,880 INFO L87 Difference]: Start difference. First operand 309 states and 418 transitions. Second operand has 22 states, 22 states have (on average 3.5454545454545454) internal successors, (78), 19 states have internal predecessors, (78), 6 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2024-11-16 07:05:41,671 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:05:41,671 INFO L93 Difference]: Finished difference Result 383 states and 520 transitions. [2024-11-16 07:05:41,671 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-11-16 07:05:41,671 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 3.5454545454545454) internal successors, (78), 19 states have internal predecessors, (78), 6 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) Word has length 78 [2024-11-16 07:05:41,671 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:05:41,673 INFO L225 Difference]: With dead ends: 383 [2024-11-16 07:05:41,673 INFO L226 Difference]: Without dead ends: 380 [2024-11-16 07:05:41,674 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 175 GetRequests, 143 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 193 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=190, Invalid=932, Unknown=0, NotChecked=0, Total=1122 [2024-11-16 07:05:41,674 INFO L432 NwaCegarLoop]: 66 mSDtfsCounter, 140 mSDsluCounter, 691 mSDsCounter, 0 mSdLazyCounter, 683 mSolverCounterSat, 91 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 142 SdHoareTripleChecker+Valid, 757 SdHoareTripleChecker+Invalid, 774 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 91 IncrementalHoareTripleChecker+Valid, 683 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2024-11-16 07:05:41,674 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [142 Valid, 757 Invalid, 774 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [91 Valid, 683 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2024-11-16 07:05:41,674 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 380 states. [2024-11-16 07:05:41,743 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 380 to 317. [2024-11-16 07:05:41,744 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 317 states, 208 states have (on average 1.1490384615384615) internal successors, (239), 215 states have internal predecessors, (239), 93 states have call successors, (93), 15 states have call predecessors, (93), 15 states have return successors, (92), 86 states have call predecessors, (92), 92 states have call successors, (92) [2024-11-16 07:05:41,745 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 317 states to 317 states and 424 transitions. [2024-11-16 07:05:41,746 INFO L78 Accepts]: Start accepts. Automaton has 317 states and 424 transitions. Word has length 78 [2024-11-16 07:05:41,746 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:05:41,746 INFO L471 AbstractCegarLoop]: Abstraction has 317 states and 424 transitions. [2024-11-16 07:05:41,746 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 3.5454545454545454) internal successors, (78), 19 states have internal predecessors, (78), 6 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2024-11-16 07:05:41,746 INFO L276 IsEmpty]: Start isEmpty. Operand 317 states and 424 transitions. [2024-11-16 07:05:41,747 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 82 [2024-11-16 07:05:41,747 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:05:41,747 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 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, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:05:41,759 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2024-11-16 07:05:41,950 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-16 07:05:41,951 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:05:41,951 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:05:41,951 INFO L85 PathProgramCache]: Analyzing trace with hash -882752627, now seen corresponding path program 2 times [2024-11-16 07:05:41,951 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:05:41,951 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1913096461] [2024-11-16 07:05:41,952 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:41,952 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:05:41,961 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:42,014 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-16 07:05:42,014 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:42,015 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-16 07:05:42,016 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:42,017 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-16 07:05:42,018 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:42,021 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-16 07:05:42,021 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:42,022 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 39 [2024-11-16 07:05:42,023 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:42,024 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 44 [2024-11-16 07:05:42,026 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:42,028 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 49 [2024-11-16 07:05:42,029 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:42,031 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 54 [2024-11-16 07:05:42,032 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:42,034 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 66 [2024-11-16 07:05:42,035 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:42,040 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 71 [2024-11-16 07:05:42,040 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:42,041 INFO L134 CoverageAnalysis]: Checked inductivity of 113 backedges. 23 proven. 0 refuted. 0 times theorem prover too weak. 90 trivial. 0 not checked. [2024-11-16 07:05:42,042 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:05:42,042 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1913096461] [2024-11-16 07:05:42,042 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1913096461] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 07:05:42,042 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 07:05:42,043 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-16 07:05:42,043 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1510986734] [2024-11-16 07:05:42,043 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 07:05:42,043 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-16 07:05:42,044 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:05:42,044 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-16 07:05:42,044 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-16 07:05:42,044 INFO L87 Difference]: Start difference. First operand 317 states and 424 transitions. Second operand has 5 states, 5 states have (on average 6.2) internal successors, (31), 5 states have internal predecessors, (31), 3 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-16 07:05:42,149 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:05:42,149 INFO L93 Difference]: Finished difference Result 543 states and 729 transitions. [2024-11-16 07:05:42,149 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-16 07:05:42,150 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 6.2) internal successors, (31), 5 states have internal predecessors, (31), 3 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 81 [2024-11-16 07:05:42,150 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:05:42,151 INFO L225 Difference]: With dead ends: 543 [2024-11-16 07:05:42,152 INFO L226 Difference]: Without dead ends: 343 [2024-11-16 07:05:42,152 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 26 GetRequests, 22 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-16 07:05:42,154 INFO L432 NwaCegarLoop]: 42 mSDtfsCounter, 1 mSDsluCounter, 98 mSDsCounter, 0 mSdLazyCounter, 43 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 140 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.0s IncrementalHoareTripleChecker+Time [2024-11-16 07:05:42,155 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 140 Invalid, 44 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 43 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-16 07:05:42,155 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 343 states. [2024-11-16 07:05:42,230 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 343 to 327. [2024-11-16 07:05:42,230 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 327 states, 218 states have (on average 1.151376146788991) internal successors, (251), 219 states have internal predecessors, (251), 93 states have call successors, (93), 15 states have call predecessors, (93), 15 states have return successors, (92), 92 states have call predecessors, (92), 92 states have call successors, (92) [2024-11-16 07:05:42,232 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 327 states to 327 states and 436 transitions. [2024-11-16 07:05:42,232 INFO L78 Accepts]: Start accepts. Automaton has 327 states and 436 transitions. Word has length 81 [2024-11-16 07:05:42,233 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:05:42,233 INFO L471 AbstractCegarLoop]: Abstraction has 327 states and 436 transitions. [2024-11-16 07:05:42,233 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 6.2) internal successors, (31), 5 states have internal predecessors, (31), 3 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-16 07:05:42,233 INFO L276 IsEmpty]: Start isEmpty. Operand 327 states and 436 transitions. [2024-11-16 07:05:42,234 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2024-11-16 07:05:42,234 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:05:42,234 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 4, 4, 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, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:05:42,234 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13 [2024-11-16 07:05:42,235 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:05:42,235 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:05:42,235 INFO L85 PathProgramCache]: Analyzing trace with hash 156730752, now seen corresponding path program 3 times [2024-11-16 07:05:42,235 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:05:42,236 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1811636705] [2024-11-16 07:05:42,236 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:42,236 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:05:42,252 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:05:42,253 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1929468604] [2024-11-16 07:05:42,253 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-16 07:05:42,253 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:05:42,253 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:05:42,255 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-16 07:05:42,256 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-16 07:05:42,303 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-16 07:05:42,304 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 07:05:42,305 INFO L255 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 65 conjuncts are in the unsatisfiable core [2024-11-16 07:05:42,307 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:05:43,052 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 21 proven. 33 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2024-11-16 07:05:43,053 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:05:50,679 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:05:50,679 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1811636705] [2024-11-16 07:05:50,679 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:05:50,679 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1929468604] [2024-11-16 07:05:50,680 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1929468604] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 07:05:50,680 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-16 07:05:50,680 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2024-11-16 07:05:50,680 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1914585295] [2024-11-16 07:05:50,680 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-16 07:05:50,680 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-16 07:05:50,680 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:05:50,680 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-16 07:05:50,681 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=99, Invalid=453, Unknown=0, NotChecked=0, Total=552 [2024-11-16 07:05:50,681 INFO L87 Difference]: Start difference. First operand 327 states and 436 transitions. Second operand has 16 states, 15 states have (on average 3.066666666666667) internal successors, (46), 14 states have internal predecessors, (46), 4 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2024-11-16 07:05:51,278 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:05:51,278 INFO L93 Difference]: Finished difference Result 405 states and 530 transitions. [2024-11-16 07:05:51,279 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-16 07:05:51,280 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 3.066666666666667) internal successors, (46), 14 states have internal predecessors, (46), 4 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) Word has length 83 [2024-11-16 07:05:51,280 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:05:51,281 INFO L225 Difference]: With dead ends: 405 [2024-11-16 07:05:51,282 INFO L226 Difference]: Without dead ends: 402 [2024-11-16 07:05:51,282 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 114 GetRequests, 85 SyntacticMatches, 0 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 141 ImplicationChecksByTransitivity, 3.6s TimeCoverageRelationStatistics Valid=167, Invalid=763, Unknown=0, NotChecked=0, Total=930 [2024-11-16 07:05:51,282 INFO L432 NwaCegarLoop]: 55 mSDtfsCounter, 63 mSDsluCounter, 549 mSDsCounter, 0 mSdLazyCounter, 471 mSolverCounterSat, 48 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 75 SdHoareTripleChecker+Valid, 604 SdHoareTripleChecker+Invalid, 519 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 48 IncrementalHoareTripleChecker+Valid, 471 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-16 07:05:51,282 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [75 Valid, 604 Invalid, 519 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [48 Valid, 471 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-16 07:05:51,283 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 402 states. [2024-11-16 07:05:51,370 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 402 to 390. [2024-11-16 07:05:51,371 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 390 states, 260 states have (on average 1.146153846153846) internal successors, (298), 261 states have internal predecessors, (298), 109 states have call successors, (109), 20 states have call predecessors, (109), 20 states have return successors, (108), 108 states have call predecessors, (108), 108 states have call successors, (108) [2024-11-16 07:05:51,372 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 390 states to 390 states and 515 transitions. [2024-11-16 07:05:51,373 INFO L78 Accepts]: Start accepts. Automaton has 390 states and 515 transitions. Word has length 83 [2024-11-16 07:05:51,373 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:05:51,373 INFO L471 AbstractCegarLoop]: Abstraction has 390 states and 515 transitions. [2024-11-16 07:05:51,373 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 3.066666666666667) internal successors, (46), 14 states have internal predecessors, (46), 4 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2024-11-16 07:05:51,373 INFO L276 IsEmpty]: Start isEmpty. Operand 390 states and 515 transitions. [2024-11-16 07:05:51,374 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 98 [2024-11-16 07:05:51,374 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:05:51,374 INFO L215 NwaCegarLoop]: trace histogram [11, 10, 10, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:05:51,387 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-16 07:05:51,577 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-16 07:05:51,578 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:05:51,578 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:05:51,578 INFO L85 PathProgramCache]: Analyzing trace with hash -382848575, now seen corresponding path program 1 times [2024-11-16 07:05:51,578 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:05:51,578 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1520899109] [2024-11-16 07:05:51,578 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:51,578 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:05:51,606 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:05:51,608 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [701099832] [2024-11-16 07:05:51,608 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:51,608 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:05:51,608 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:05:51,610 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-16 07:05:51,611 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-16 07:05:51,654 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:51,655 INFO L255 TraceCheckSpWp]: Trace formula consists of 210 conjuncts, 32 conjuncts are in the unsatisfiable core [2024-11-16 07:05:51,656 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:05:51,969 INFO L134 CoverageAnalysis]: Checked inductivity of 244 backedges. 26 proven. 23 refuted. 0 times theorem prover too weak. 195 trivial. 0 not checked. [2024-11-16 07:05:51,969 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:05:52,256 INFO L134 CoverageAnalysis]: Checked inductivity of 244 backedges. 23 proven. 17 refuted. 0 times theorem prover too weak. 204 trivial. 0 not checked. [2024-11-16 07:05:52,257 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:05:52,257 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1520899109] [2024-11-16 07:05:52,257 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:05:52,257 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [701099832] [2024-11-16 07:05:52,257 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [701099832] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 07:05:52,257 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-16 07:05:52,257 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 10] total 22 [2024-11-16 07:05:52,257 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [533815407] [2024-11-16 07:05:52,257 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-16 07:05:52,257 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-11-16 07:05:52,257 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:05:52,258 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-16 07:05:52,258 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=89, Invalid=373, Unknown=0, NotChecked=0, Total=462 [2024-11-16 07:05:52,258 INFO L87 Difference]: Start difference. First operand 390 states and 515 transitions. Second operand has 22 states, 22 states have (on average 2.5454545454545454) internal successors, (56), 19 states have internal predecessors, (56), 8 states have call successors, (27), 3 states have call predecessors, (27), 2 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) [2024-11-16 07:05:54,263 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:05:54,263 INFO L93 Difference]: Finished difference Result 979 states and 1449 transitions. [2024-11-16 07:05:54,264 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2024-11-16 07:05:54,264 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 2.5454545454545454) internal successors, (56), 19 states have internal predecessors, (56), 8 states have call successors, (27), 3 states have call predecessors, (27), 2 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) Word has length 97 [2024-11-16 07:05:54,264 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:05:54,268 INFO L225 Difference]: With dead ends: 979 [2024-11-16 07:05:54,268 INFO L226 Difference]: Without dead ends: 976 [2024-11-16 07:05:54,269 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 220 GetRequests, 173 SyntacticMatches, 0 SemanticMatches, 47 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 561 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=528, Invalid=1824, Unknown=0, NotChecked=0, Total=2352 [2024-11-16 07:05:54,270 INFO L432 NwaCegarLoop]: 51 mSDtfsCounter, 184 mSDsluCounter, 512 mSDsCounter, 0 mSdLazyCounter, 480 mSolverCounterSat, 127 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 188 SdHoareTripleChecker+Valid, 563 SdHoareTripleChecker+Invalid, 607 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 127 IncrementalHoareTripleChecker+Valid, 480 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2024-11-16 07:05:54,270 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [188 Valid, 563 Invalid, 607 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [127 Valid, 480 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2024-11-16 07:05:54,271 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 976 states. [2024-11-16 07:05:54,571 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 976 to 787. [2024-11-16 07:05:54,572 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 787 states, 458 states have (on average 1.2096069868995634) internal successors, (554), 459 states have internal predecessors, (554), 305 states have call successors, (305), 23 states have call predecessors, (305), 23 states have return successors, (304), 304 states have call predecessors, (304), 304 states have call successors, (304) [2024-11-16 07:05:54,575 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 787 states to 787 states and 1163 transitions. [2024-11-16 07:05:54,576 INFO L78 Accepts]: Start accepts. Automaton has 787 states and 1163 transitions. Word has length 97 [2024-11-16 07:05:54,576 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:05:54,576 INFO L471 AbstractCegarLoop]: Abstraction has 787 states and 1163 transitions. [2024-11-16 07:05:54,577 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 2.5454545454545454) internal successors, (56), 19 states have internal predecessors, (56), 8 states have call successors, (27), 3 states have call predecessors, (27), 2 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) [2024-11-16 07:05:54,577 INFO L276 IsEmpty]: Start isEmpty. Operand 787 states and 1163 transitions. [2024-11-16 07:05:54,577 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2024-11-16 07:05:54,577 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:05:54,578 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 3, 3, 3, 3, 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, 1, 1, 1, 1, 1, 1] [2024-11-16 07:05:54,591 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-16 07:05:54,778 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-16 07:05:54,778 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:05:54,778 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:05:54,778 INFO L85 PathProgramCache]: Analyzing trace with hash -1581530788, now seen corresponding path program 1 times [2024-11-16 07:05:54,778 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:05:54,779 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [721054241] [2024-11-16 07:05:54,779 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:54,779 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:05:54,794 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:05:54,798 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [580168987] [2024-11-16 07:05:54,798 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:54,798 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:05:54,798 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:05:54,800 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-16 07:05:54,800 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-16 07:05:54,846 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:54,847 INFO L255 TraceCheckSpWp]: Trace formula consists of 224 conjuncts, 71 conjuncts are in the unsatisfiable core [2024-11-16 07:05:54,849 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:05:56,329 INFO L134 CoverageAnalysis]: Checked inductivity of 178 backedges. 36 proven. 39 refuted. 0 times theorem prover too weak. 103 trivial. 0 not checked. [2024-11-16 07:05:56,329 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:06:04,810 INFO L134 CoverageAnalysis]: Checked inductivity of 178 backedges. 30 proven. 33 refuted. 0 times theorem prover too weak. 115 trivial. 0 not checked. [2024-11-16 07:06:04,810 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:06:04,811 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [721054241] [2024-11-16 07:06:04,811 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:06:04,811 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [580168987] [2024-11-16 07:06:04,811 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [580168987] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 07:06:04,811 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-16 07:06:04,811 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 17] total 36 [2024-11-16 07:06:04,811 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2143624440] [2024-11-16 07:06:04,811 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-16 07:06:04,812 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 36 states [2024-11-16 07:06:04,812 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:06:04,812 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2024-11-16 07:06:04,813 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=169, Invalid=1091, Unknown=0, NotChecked=0, Total=1260 [2024-11-16 07:06:04,813 INFO L87 Difference]: Start difference. First operand 787 states and 1163 transitions. Second operand has 36 states, 33 states have (on average 2.393939393939394) internal successors, (79), 33 states have internal predecessors, (79), 11 states have call successors, (24), 3 states have call predecessors, (24), 3 states have return successors, (23), 9 states have call predecessors, (23), 9 states have call successors, (23) [2024-11-16 07:07:00,566 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [1] [2024-11-16 07:07:09,332 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.29s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [1]