./Ultimate.py --spec /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/properties/unreach-call.prp --file /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound100.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 4a390ef5 Calling Ultimate with: /root/.sdkman/candidates/java/current/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 /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound100.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 f5697d76d3e5ae232d0e056ee307ac88ca38e983a94c4765bc5d51f77e79d2f7 --- Real Ultimate output --- This is Ultimate 0.2.5-dev-4a390ef-m [2024-10-24 00:10:46,965 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-10-24 00:10:47,063 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-10-24 00:10:47,069 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-10-24 00:10:47,071 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-10-24 00:10:47,101 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-10-24 00:10:47,101 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-10-24 00:10:47,102 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-10-24 00:10:47,104 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-10-24 00:10:47,105 INFO L153 SettingsManager]: * Use memory slicer=true [2024-10-24 00:10:47,106 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-10-24 00:10:47,107 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-10-24 00:10:47,107 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-10-24 00:10:47,108 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-10-24 00:10:47,110 INFO L153 SettingsManager]: * Use SBE=true [2024-10-24 00:10:47,110 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-10-24 00:10:47,110 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-10-24 00:10:47,111 INFO L153 SettingsManager]: * sizeof long=4 [2024-10-24 00:10:47,111 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-10-24 00:10:47,111 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-10-24 00:10:47,115 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-10-24 00:10:47,116 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-10-24 00:10:47,116 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-10-24 00:10:47,116 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-10-24 00:10:47,116 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-10-24 00:10:47,117 INFO L153 SettingsManager]: * sizeof long double=12 [2024-10-24 00:10:47,117 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-10-24 00:10:47,117 INFO L153 SettingsManager]: * Use constant arrays=true [2024-10-24 00:10:47,117 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-10-24 00:10:47,118 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-10-24 00:10:47,118 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-10-24 00:10:47,118 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-10-24 00:10:47,118 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-24 00:10:47,119 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-10-24 00:10:47,119 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-10-24 00:10:47,121 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-10-24 00:10:47,121 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-10-24 00:10:47,122 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-10-24 00:10:47,122 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-10-24 00:10:47,122 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-10-24 00:10:47,122 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-10-24 00:10:47,123 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-10-24 00:10:47,123 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 -> f5697d76d3e5ae232d0e056ee307ac88ca38e983a94c4765bc5d51f77e79d2f7 [2024-10-24 00:10:47,395 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-10-24 00:10:47,421 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-10-24 00:10:47,424 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-10-24 00:10:47,425 INFO L270 PluginConnector]: Initializing CDTParser... [2024-10-24 00:10:47,426 INFO L274 PluginConnector]: CDTParser initialized [2024-10-24 00:10:47,427 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound100.c [2024-10-24 00:10:48,919 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-10-24 00:10:49,101 INFO L384 CDTParser]: Found 1 translation units. [2024-10-24 00:10:49,101 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound100.c [2024-10-24 00:10:49,109 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/6fe6b689b/7dc2c5812318496193a3c0baa3d4fc28/FLAG8c41b8070 [2024-10-24 00:10:49,121 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/6fe6b689b/7dc2c5812318496193a3c0baa3d4fc28 [2024-10-24 00:10:49,123 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-10-24 00:10:49,124 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-10-24 00:10:49,126 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-10-24 00:10:49,126 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-10-24 00:10:49,133 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-10-24 00:10:49,133 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 24.10 12:10:49" (1/1) ... [2024-10-24 00:10:49,134 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1122ec2d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:10:49, skipping insertion in model container [2024-10-24 00:10:49,134 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 24.10 12:10:49" (1/1) ... [2024-10-24 00:10:49,160 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-10-24 00:10:49,345 WARN L248 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/egcd2-ll_valuebound100.c[490,503] [2024-10-24 00:10:49,376 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-24 00:10:49,383 INFO L200 MainTranslator]: Completed pre-run [2024-10-24 00:10:49,400 WARN L248 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/egcd2-ll_valuebound100.c[490,503] [2024-10-24 00:10:49,411 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-24 00:10:49,428 INFO L204 MainTranslator]: Completed translation [2024-10-24 00:10:49,431 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:10:49 WrapperNode [2024-10-24 00:10:49,431 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-10-24 00:10:49,433 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-10-24 00:10:49,433 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-10-24 00:10:49,434 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-10-24 00:10:49,441 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:10:49" (1/1) ... [2024-10-24 00:10:49,453 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:10:49" (1/1) ... [2024-10-24 00:10:49,472 INFO L138 Inliner]: procedures = 14, calls = 19, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 79 [2024-10-24 00:10:49,473 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-10-24 00:10:49,473 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-10-24 00:10:49,473 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-10-24 00:10:49,474 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-10-24 00:10:49,481 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:10:49" (1/1) ... [2024-10-24 00:10:49,482 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:10:49" (1/1) ... [2024-10-24 00:10:49,484 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:10:49" (1/1) ... [2024-10-24 00:10:49,498 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-10-24 00:10:49,499 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:10:49" (1/1) ... [2024-10-24 00:10:49,499 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:10:49" (1/1) ... [2024-10-24 00:10:49,507 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:10:49" (1/1) ... [2024-10-24 00:10:49,511 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:10:49" (1/1) ... [2024-10-24 00:10:49,512 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:10:49" (1/1) ... [2024-10-24 00:10:49,513 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:10:49" (1/1) ... [2024-10-24 00:10:49,518 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-10-24 00:10:49,519 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-10-24 00:10:49,519 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-10-24 00:10:49,519 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-10-24 00:10:49,520 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:10:49" (1/1) ... [2024-10-24 00:10:49,529 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-24 00:10:49,540 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:10:49,571 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-10-24 00:10:49,575 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-10-24 00:10:49,623 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-10-24 00:10:49,623 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-10-24 00:10:49,624 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-10-24 00:10:49,624 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-10-24 00:10:49,624 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-10-24 00:10:49,624 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-10-24 00:10:49,624 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-10-24 00:10:49,625 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-10-24 00:10:49,682 INFO L238 CfgBuilder]: Building ICFG [2024-10-24 00:10:49,684 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-10-24 00:10:49,830 INFO L? ?]: Removed 11 outVars from TransFormulas that were not future-live. [2024-10-24 00:10:49,830 INFO L287 CfgBuilder]: Performing block encoding [2024-10-24 00:10:49,858 INFO L309 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-10-24 00:10:49,858 INFO L314 CfgBuilder]: Removed 2 assume(true) statements. [2024-10-24 00:10:49,859 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.10 12:10:49 BoogieIcfgContainer [2024-10-24 00:10:49,859 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-10-24 00:10:49,861 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-10-24 00:10:49,862 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-10-24 00:10:49,865 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-10-24 00:10:49,865 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 24.10 12:10:49" (1/3) ... [2024-10-24 00:10:49,865 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7c6732a9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.10 12:10:49, skipping insertion in model container [2024-10-24 00:10:49,866 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:10:49" (2/3) ... [2024-10-24 00:10:49,866 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7c6732a9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.10 12:10:49, skipping insertion in model container [2024-10-24 00:10:49,866 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.10 12:10:49" (3/3) ... [2024-10-24 00:10:49,867 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd2-ll_valuebound100.c [2024-10-24 00:10:49,882 INFO L209 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-10-24 00:10:49,882 INFO L149 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-10-24 00:10:49,937 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-10-24 00:10:49,944 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;@4c94bf85, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-10-24 00:10:49,945 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-10-24 00:10:49,949 INFO L276 IsEmpty]: Start isEmpty. Operand has 32 states, 16 states have (on average 1.5625) internal successors, (25), 18 states have internal predecessors, (25), 12 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-10-24 00:10:49,955 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2024-10-24 00:10:49,955 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:10:49,956 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:10:49,956 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:10:49,960 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:10:49,961 INFO L85 PathProgramCache]: Analyzing trace with hash 1865535902, now seen corresponding path program 1 times [2024-10-24 00:10:49,968 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:10:49,968 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1347071643] [2024-10-24 00:10:49,968 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:10:49,969 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:10:50,055 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:10:50,119 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-24 00:10:50,123 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:10:50,131 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-24 00:10:50,134 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:10:50,138 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-24 00:10:50,140 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:10:50,143 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-24 00:10:50,145 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:10:50,148 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-10-24 00:10:50,149 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:10:50,157 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2024-10-24 00:10:50,159 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:10:50,164 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-10-24 00:10:50,165 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:10:50,165 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1347071643] [2024-10-24 00:10:50,166 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1347071643] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 00:10:50,166 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-24 00:10:50,167 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-10-24 00:10:50,168 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [28549244] [2024-10-24 00:10:50,169 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 00:10:50,173 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-10-24 00:10:50,173 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:10:50,213 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-10-24 00:10:50,213 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-10-24 00:10:50,216 INFO L87 Difference]: Start difference. First operand has 32 states, 16 states have (on average 1.5625) internal successors, (25), 18 states have internal predecessors, (25), 12 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 2 states have call successors, (6) [2024-10-24 00:10:50,241 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:10:50,241 INFO L93 Difference]: Finished difference Result 62 states and 107 transitions. [2024-10-24 00:10:50,243 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-10-24 00:10:50,244 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 2 states have call successors, (6) Word has length 38 [2024-10-24 00:10:50,245 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:10:50,250 INFO L225 Difference]: With dead ends: 62 [2024-10-24 00:10:50,251 INFO L226 Difference]: Without dead ends: 30 [2024-10-24 00:10:50,254 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 20 GetRequests, 20 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-10-24 00:10:50,258 INFO L432 NwaCegarLoop]: 41 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 2 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 41 SdHoareTripleChecker+Invalid, 2 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 2 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-24 00:10:50,259 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 41 Invalid, 2 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 2 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-24 00:10:50,272 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2024-10-24 00:10:50,287 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 30. [2024-10-24 00:10:50,289 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 15 states have (on average 1.2) internal successors, (18), 17 states have internal predecessors, (18), 12 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-10-24 00:10:50,290 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 41 transitions. [2024-10-24 00:10:50,292 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 41 transitions. Word has length 38 [2024-10-24 00:10:50,292 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:10:50,294 INFO L471 AbstractCegarLoop]: Abstraction has 30 states and 41 transitions. [2024-10-24 00:10:50,294 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 2 states have call successors, (6) [2024-10-24 00:10:50,294 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 41 transitions. [2024-10-24 00:10:50,296 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2024-10-24 00:10:50,297 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:10:50,298 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:10:50,298 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-10-24 00:10:50,298 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:10:50,299 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:10:50,300 INFO L85 PathProgramCache]: Analyzing trace with hash -279596905, now seen corresponding path program 1 times [2024-10-24 00:10:50,301 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:10:50,301 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [658129788] [2024-10-24 00:10:50,301 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:10:50,302 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:10:50,349 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:10:50,578 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-24 00:10:50,580 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:10:50,585 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-24 00:10:50,588 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:10:50,592 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-24 00:10:50,595 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:10:50,601 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-24 00:10:50,603 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:10:50,643 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-10-24 00:10:50,646 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:10:50,654 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2024-10-24 00:10:50,656 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:10:50,660 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 9 proven. 6 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-10-24 00:10:50,660 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:10:50,661 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [658129788] [2024-10-24 00:10:50,661 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [658129788] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 00:10:50,661 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1071664968] [2024-10-24 00:10:50,661 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:10:50,662 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:10:50,662 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:10:50,664 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-10-24 00:10:50,666 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-10-24 00:10:50,754 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:10:50,761 INFO L255 TraceCheckSpWp]: Trace formula consists of 111 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-10-24 00:10:50,768 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:10:51,041 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 3 proven. 12 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-10-24 00:10:51,043 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:10:51,239 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1071664968] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 00:10:51,241 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-24 00:10:51,241 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 9] total 11 [2024-10-24 00:10:51,242 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1958829483] [2024-10-24 00:10:51,243 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-24 00:10:51,243 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-10-24 00:10:51,244 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:10:51,245 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-10-24 00:10:51,247 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=174, Unknown=0, NotChecked=0, Total=210 [2024-10-24 00:10:51,248 INFO L87 Difference]: Start difference. First operand 30 states and 41 transitions. Second operand has 11 states, 10 states have (on average 1.9) internal successors, (19), 8 states have internal predecessors, (19), 6 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) [2024-10-24 00:10:51,516 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:10:51,517 INFO L93 Difference]: Finished difference Result 51 states and 68 transitions. [2024-10-24 00:10:51,517 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-10-24 00:10:51,518 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 1.9) internal successors, (19), 8 states have internal predecessors, (19), 6 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) Word has length 39 [2024-10-24 00:10:51,518 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:10:51,519 INFO L225 Difference]: With dead ends: 51 [2024-10-24 00:10:51,521 INFO L226 Difference]: Without dead ends: 43 [2024-10-24 00:10:51,521 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 49 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=54, Invalid=252, Unknown=0, NotChecked=0, Total=306 [2024-10-24 00:10:51,523 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 33 mSDsluCounter, 179 mSDsCounter, 0 mSdLazyCounter, 160 mSolverCounterSat, 25 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 207 SdHoareTripleChecker+Invalid, 185 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 25 IncrementalHoareTripleChecker+Valid, 160 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-10-24 00:10:51,525 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [33 Valid, 207 Invalid, 185 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [25 Valid, 160 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-10-24 00:10:51,526 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2024-10-24 00:10:51,543 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 42. [2024-10-24 00:10:51,549 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 42 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 23 states have internal predecessors, (26), 16 states have call successors, (16), 3 states have call predecessors, (16), 3 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2024-10-24 00:10:51,551 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 57 transitions. [2024-10-24 00:10:51,552 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 57 transitions. Word has length 39 [2024-10-24 00:10:51,552 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:10:51,554 INFO L471 AbstractCegarLoop]: Abstraction has 42 states and 57 transitions. [2024-10-24 00:10:51,555 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 1.9) internal successors, (19), 8 states have internal predecessors, (19), 6 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) [2024-10-24 00:10:51,555 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 57 transitions. [2024-10-24 00:10:51,556 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2024-10-24 00:10:51,556 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:10:51,557 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:10:51,572 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2024-10-24 00:10:51,757 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:10:51,758 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:10:51,758 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:10:51,758 INFO L85 PathProgramCache]: Analyzing trace with hash -76887146, now seen corresponding path program 1 times [2024-10-24 00:10:51,759 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:10:51,759 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [418650056] [2024-10-24 00:10:51,759 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:10:51,759 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:10:51,782 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:10:51,785 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1663311074] [2024-10-24 00:10:51,786 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:10:51,786 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:10:51,786 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:10:51,788 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-10-24 00:10:51,791 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-10-24 00:10:51,849 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:10:51,850 INFO L255 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-24 00:10:51,853 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:10:51,901 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-10-24 00:10:51,902 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-24 00:10:51,902 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:10:51,902 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [418650056] [2024-10-24 00:10:51,906 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 00:10:51,906 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1663311074] [2024-10-24 00:10:51,906 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1663311074] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 00:10:51,907 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-24 00:10:51,907 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-24 00:10:51,907 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1808294173] [2024-10-24 00:10:51,907 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 00:10:51,908 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-24 00:10:51,908 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:10:51,908 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-24 00:10:51,909 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-24 00:10:51,909 INFO L87 Difference]: Start difference. First operand 42 states and 57 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2024-10-24 00:10:51,967 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:10:51,968 INFO L93 Difference]: Finished difference Result 61 states and 85 transitions. [2024-10-24 00:10:51,968 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-24 00:10:51,969 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) Word has length 40 [2024-10-24 00:10:51,969 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:10:51,970 INFO L225 Difference]: With dead ends: 61 [2024-10-24 00:10:51,971 INFO L226 Difference]: Without dead ends: 59 [2024-10-24 00:10:51,971 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 36 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-10-24 00:10:51,972 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 4 mSDsluCounter, 95 mSDsCounter, 0 mSdLazyCounter, 34 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 129 SdHoareTripleChecker+Invalid, 34 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 34 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-24 00:10:51,973 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 129 Invalid, 34 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 34 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-24 00:10:51,974 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2024-10-24 00:10:51,992 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 50. [2024-10-24 00:10:51,993 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 27 states have (on average 1.1481481481481481) internal successors, (31), 30 states have internal predecessors, (31), 18 states have call successors, (18), 4 states have call predecessors, (18), 4 states have return successors, (17), 15 states have call predecessors, (17), 17 states have call successors, (17) [2024-10-24 00:10:51,997 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 66 transitions. [2024-10-24 00:10:51,998 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 66 transitions. Word has length 40 [2024-10-24 00:10:52,002 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:10:52,002 INFO L471 AbstractCegarLoop]: Abstraction has 50 states and 66 transitions. [2024-10-24 00:10:52,002 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2024-10-24 00:10:52,002 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 66 transitions. [2024-10-24 00:10:52,003 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2024-10-24 00:10:52,003 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:10:52,004 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 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-10-24 00:10:52,024 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-10-24 00:10:52,204 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2024-10-24 00:10:52,205 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:10:52,206 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:10:52,206 INFO L85 PathProgramCache]: Analyzing trace with hash 345761675, now seen corresponding path program 1 times [2024-10-24 00:10:52,206 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:10:52,206 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2122585617] [2024-10-24 00:10:52,206 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:10:52,207 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:10:52,230 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:10:52,232 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1016395615] [2024-10-24 00:10:52,232 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:10:52,233 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:10:52,233 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:10:52,235 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-10-24 00:10:52,239 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-10-24 00:10:52,291 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:10:52,292 INFO L255 TraceCheckSpWp]: Trace formula consists of 124 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-10-24 00:10:52,294 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:10:52,365 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-10-24 00:10:52,365 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-24 00:10:52,365 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:10:52,366 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2122585617] [2024-10-24 00:10:52,366 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 00:10:52,366 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1016395615] [2024-10-24 00:10:52,366 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1016395615] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 00:10:52,366 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-24 00:10:52,366 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-24 00:10:52,366 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [66382715] [2024-10-24 00:10:52,367 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 00:10:52,367 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-24 00:10:52,367 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:10:52,368 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-24 00:10:52,368 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-24 00:10:52,368 INFO L87 Difference]: Start difference. First operand 50 states and 66 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 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-10-24 00:10:52,413 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:10:52,413 INFO L93 Difference]: Finished difference Result 57 states and 72 transitions. [2024-10-24 00:10:52,414 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-24 00:10:52,414 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 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 45 [2024-10-24 00:10:52,414 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:10:52,418 INFO L225 Difference]: With dead ends: 57 [2024-10-24 00:10:52,418 INFO L226 Difference]: Without dead ends: 55 [2024-10-24 00:10:52,418 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 45 GetRequests, 41 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-10-24 00:10:52,421 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 5 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 30 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 139 SdHoareTripleChecker+Invalid, 30 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 30 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-24 00:10:52,422 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 139 Invalid, 30 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 30 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-24 00:10:52,422 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2024-10-24 00:10:52,437 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 54. [2024-10-24 00:10:52,438 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 30 states have (on average 1.1333333333333333) internal successors, (34), 33 states have internal predecessors, (34), 18 states have call successors, (18), 5 states have call predecessors, (18), 5 states have return successors, (17), 15 states have call predecessors, (17), 17 states have call successors, (17) [2024-10-24 00:10:52,440 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 69 transitions. [2024-10-24 00:10:52,441 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 69 transitions. Word has length 45 [2024-10-24 00:10:52,442 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:10:52,442 INFO L471 AbstractCegarLoop]: Abstraction has 54 states and 69 transitions. [2024-10-24 00:10:52,442 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 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-10-24 00:10:52,442 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 69 transitions. [2024-10-24 00:10:52,443 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2024-10-24 00:10:52,443 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:10:52,444 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 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] [2024-10-24 00:10:52,462 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-10-24 00:10:52,647 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:10:52,648 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:10:52,648 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:10:52,648 INFO L85 PathProgramCache]: Analyzing trace with hash -2047387093, now seen corresponding path program 1 times [2024-10-24 00:10:52,649 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:10:52,649 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1415281009] [2024-10-24 00:10:52,649 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:10:52,649 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:10:52,683 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:10:52,687 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1850955771] [2024-10-24 00:10:52,690 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:10:52,690 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:10:52,691 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:10:52,695 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-10-24 00:10:52,697 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-10-24 00:10:52,774 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:10:52,775 INFO L255 TraceCheckSpWp]: Trace formula consists of 142 conjuncts, 25 conjuncts are in the unsatisfiable core [2024-10-24 00:10:52,778 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:10:53,077 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 8 proven. 4 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2024-10-24 00:10:53,078 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:10:53,135 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:10:53,135 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1415281009] [2024-10-24 00:10:53,136 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 00:10:53,136 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1850955771] [2024-10-24 00:10:53,136 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1850955771] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 00:10:53,136 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-24 00:10:53,136 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2024-10-24 00:10:53,136 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1683746982] [2024-10-24 00:10:53,137 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-24 00:10:53,137 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-10-24 00:10:53,137 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:10:53,138 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-10-24 00:10:53,138 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2024-10-24 00:10:53,138 INFO L87 Difference]: Start difference. First operand 54 states and 69 transitions. Second operand has 8 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 3 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-10-24 00:10:53,264 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:10:53,265 INFO L93 Difference]: Finished difference Result 61 states and 75 transitions. [2024-10-24 00:10:53,265 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-10-24 00:10:53,266 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 3 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 55 [2024-10-24 00:10:53,267 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:10:53,271 INFO L225 Difference]: With dead ends: 61 [2024-10-24 00:10:53,271 INFO L226 Difference]: Without dead ends: 59 [2024-10-24 00:10:53,271 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 60 GetRequests, 51 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=29, Invalid=81, Unknown=0, NotChecked=0, Total=110 [2024-10-24 00:10:53,273 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 7 mSDsluCounter, 120 mSDsCounter, 0 mSdLazyCounter, 100 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 150 SdHoareTripleChecker+Invalid, 103 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 100 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-24 00:10:53,274 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 150 Invalid, 103 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 100 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-24 00:10:53,274 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2024-10-24 00:10:53,290 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 58. [2024-10-24 00:10:53,291 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 33 states have (on average 1.121212121212121) internal successors, (37), 36 states have internal predecessors, (37), 18 states have call successors, (18), 6 states have call predecessors, (18), 6 states have return successors, (17), 15 states have call predecessors, (17), 17 states have call successors, (17) [2024-10-24 00:10:53,293 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 72 transitions. [2024-10-24 00:10:53,293 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 72 transitions. Word has length 55 [2024-10-24 00:10:53,294 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:10:53,295 INFO L471 AbstractCegarLoop]: Abstraction has 58 states and 72 transitions. [2024-10-24 00:10:53,295 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 3 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-10-24 00:10:53,295 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 72 transitions. [2024-10-24 00:10:53,296 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2024-10-24 00:10:53,296 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:10:53,298 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 5, 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, 1, 1, 1, 1] [2024-10-24 00:10:53,315 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-10-24 00:10:53,501 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:10:53,502 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:10:53,502 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:10:53,502 INFO L85 PathProgramCache]: Analyzing trace with hash 1705825109, now seen corresponding path program 1 times [2024-10-24 00:10:53,502 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:10:53,502 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2121414547] [2024-10-24 00:10:53,503 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:10:53,503 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:10:53,532 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:10:53,535 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [246678126] [2024-10-24 00:10:53,536 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:10:53,536 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:10:53,536 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:10:53,540 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-10-24 00:10:53,542 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-10-24 00:10:53,602 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:10:53,604 INFO L255 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-24 00:10:53,606 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:10:53,679 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2024-10-24 00:10:53,680 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:10:53,788 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2024-10-24 00:10:53,788 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:10:53,788 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2121414547] [2024-10-24 00:10:53,789 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 00:10:53,789 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [246678126] [2024-10-24 00:10:53,789 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [246678126] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-24 00:10:53,789 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-24 00:10:53,789 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2024-10-24 00:10:53,789 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1475219963] [2024-10-24 00:10:53,789 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-24 00:10:53,790 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-10-24 00:10:53,790 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:10:53,790 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-10-24 00:10:53,790 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-10-24 00:10:53,790 INFO L87 Difference]: Start difference. First operand 58 states and 72 transitions. Second operand has 7 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 6 states have internal predecessors, (19), 4 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2024-10-24 00:10:53,910 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:10:53,910 INFO L93 Difference]: Finished difference Result 86 states and 117 transitions. [2024-10-24 00:10:53,911 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-10-24 00:10:53,911 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 6 states have internal predecessors, (19), 4 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) Word has length 62 [2024-10-24 00:10:53,911 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:10:53,912 INFO L225 Difference]: With dead ends: 86 [2024-10-24 00:10:53,912 INFO L226 Difference]: Without dead ends: 84 [2024-10-24 00:10:53,912 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 123 GetRequests, 114 SyntacticMatches, 3 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-10-24 00:10:53,913 INFO L432 NwaCegarLoop]: 42 mSDtfsCounter, 6 mSDsluCounter, 170 mSDsCounter, 0 mSdLazyCounter, 75 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 212 SdHoareTripleChecker+Invalid, 77 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 75 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-24 00:10:53,913 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 212 Invalid, 77 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 75 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-24 00:10:53,914 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 84 states. [2024-10-24 00:10:53,934 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 84 to 54. [2024-10-24 00:10:53,935 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 31 states have (on average 1.1290322580645162) internal successors, (35), 32 states have internal predecessors, (35), 16 states have call successors, (16), 6 states have call predecessors, (16), 6 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2024-10-24 00:10:53,935 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 66 transitions. [2024-10-24 00:10:53,937 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 66 transitions. Word has length 62 [2024-10-24 00:10:53,937 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:10:53,937 INFO L471 AbstractCegarLoop]: Abstraction has 54 states and 66 transitions. [2024-10-24 00:10:53,938 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 6 states have internal predecessors, (19), 4 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2024-10-24 00:10:53,938 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 66 transitions. [2024-10-24 00:10:53,939 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2024-10-24 00:10:53,939 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:10:53,939 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 5, 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, 1, 1, 1] [2024-10-24 00:10:53,957 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-10-24 00:10:54,143 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:10:54,144 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:10:54,144 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:10:54,144 INFO L85 PathProgramCache]: Analyzing trace with hash 392643903, now seen corresponding path program 1 times [2024-10-24 00:10:54,144 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:10:54,144 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1603404080] [2024-10-24 00:10:54,145 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:10:54,145 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:10:54,168 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:10:54,312 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-24 00:10:54,313 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:10:54,316 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-24 00:10:54,317 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:10:54,319 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-24 00:10:54,320 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:10:54,342 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-24 00:10:54,344 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:10:54,347 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-10-24 00:10:54,348 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:10:54,351 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2024-10-24 00:10:54,352 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:10:54,355 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2024-10-24 00:10:54,356 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:10:54,359 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 41 [2024-10-24 00:10:54,360 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:10:54,363 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 46 [2024-10-24 00:10:54,364 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:10:54,367 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 51 [2024-10-24 00:10:54,368 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:10:54,371 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 14 proven. 11 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2024-10-24 00:10:54,372 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:10:54,372 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1603404080] [2024-10-24 00:10:54,372 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1603404080] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 00:10:54,372 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1462261039] [2024-10-24 00:10:54,372 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:10:54,372 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:10:54,372 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:10:54,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-10-24 00:10:54,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-10-24 00:10:54,440 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:10:54,443 INFO L255 TraceCheckSpWp]: Trace formula consists of 167 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-10-24 00:10:54,446 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:10:54,484 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 14 proven. 11 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2024-10-24 00:10:54,485 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:10:54,599 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 14 proven. 11 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2024-10-24 00:10:54,600 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1462261039] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-24 00:10:54,600 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-24 00:10:54,600 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 9 [2024-10-24 00:10:54,600 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [114916896] [2024-10-24 00:10:54,600 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-24 00:10:54,601 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-10-24 00:10:54,601 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:10:54,602 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-10-24 00:10:54,602 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2024-10-24 00:10:54,602 INFO L87 Difference]: Start difference. First operand 54 states and 66 transitions. Second operand has 9 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 8 states have internal predecessors, (24), 5 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2024-10-24 00:10:54,781 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:10:54,781 INFO L93 Difference]: Finished difference Result 101 states and 141 transitions. [2024-10-24 00:10:54,781 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-10-24 00:10:54,782 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 8 states have internal predecessors, (24), 5 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) Word has length 64 [2024-10-24 00:10:54,782 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:10:54,783 INFO L225 Difference]: With dead ends: 101 [2024-10-24 00:10:54,783 INFO L226 Difference]: Without dead ends: 93 [2024-10-24 00:10:54,784 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 157 GetRequests, 142 SyntacticMatches, 4 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=42, Invalid=114, Unknown=0, NotChecked=0, Total=156 [2024-10-24 00:10:54,785 INFO L432 NwaCegarLoop]: 42 mSDtfsCounter, 32 mSDsluCounter, 207 mSDsCounter, 0 mSdLazyCounter, 103 mSolverCounterSat, 30 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 37 SdHoareTripleChecker+Valid, 249 SdHoareTripleChecker+Invalid, 133 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 30 IncrementalHoareTripleChecker+Valid, 103 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-24 00:10:54,785 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [37 Valid, 249 Invalid, 133 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [30 Valid, 103 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-24 00:10:54,786 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2024-10-24 00:10:54,805 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 84. [2024-10-24 00:10:54,806 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 84 states, 45 states have (on average 1.2) internal successors, (54), 46 states have internal predecessors, (54), 32 states have call successors, (32), 6 states have call predecessors, (32), 6 states have return successors, (31), 31 states have call predecessors, (31), 31 states have call successors, (31) [2024-10-24 00:10:54,807 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 84 states to 84 states and 117 transitions. [2024-10-24 00:10:54,807 INFO L78 Accepts]: Start accepts. Automaton has 84 states and 117 transitions. Word has length 64 [2024-10-24 00:10:54,808 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:10:54,808 INFO L471 AbstractCegarLoop]: Abstraction has 84 states and 117 transitions. [2024-10-24 00:10:54,808 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 8 states have internal predecessors, (24), 5 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2024-10-24 00:10:54,808 INFO L276 IsEmpty]: Start isEmpty. Operand 84 states and 117 transitions. [2024-10-24 00:10:54,809 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2024-10-24 00:10:54,809 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:10:54,809 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 6, 5, 5, 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-10-24 00:10:54,827 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-10-24 00:10:55,010 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:10:55,011 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:10:55,011 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:10:55,011 INFO L85 PathProgramCache]: Analyzing trace with hash -45785549, now seen corresponding path program 1 times [2024-10-24 00:10:55,011 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:10:55,011 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [444878525] [2024-10-24 00:10:55,011 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:10:55,011 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:10:55,038 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:10:55,040 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [43727296] [2024-10-24 00:10:55,041 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:10:55,042 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:10:55,042 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:10:55,044 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-10-24 00:10:55,045 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-10-24 00:10:55,108 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:10:55,109 INFO L255 TraceCheckSpWp]: Trace formula consists of 180 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-10-24 00:10:55,112 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:10:55,238 INFO L134 CoverageAnalysis]: Checked inductivity of 115 backedges. 10 proven. 5 refuted. 0 times theorem prover too weak. 100 trivial. 0 not checked. [2024-10-24 00:10:55,238 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:10:55,274 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:10:55,275 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [444878525] [2024-10-24 00:10:55,275 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 00:10:55,275 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [43727296] [2024-10-24 00:10:55,275 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [43727296] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 00:10:55,275 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-24 00:10:55,275 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6] total 6 [2024-10-24 00:10:55,275 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1622156695] [2024-10-24 00:10:55,275 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-24 00:10:55,276 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-10-24 00:10:55,276 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:10:55,276 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-10-24 00:10:55,276 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2024-10-24 00:10:55,276 INFO L87 Difference]: Start difference. First operand 84 states and 117 transitions. Second operand has 6 states, 6 states have (on average 3.3333333333333335) internal successors, (20), 5 states have internal predecessors, (20), 3 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2024-10-24 00:10:55,398 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:10:55,399 INFO L93 Difference]: Finished difference Result 119 states and 168 transitions. [2024-10-24 00:10:55,399 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-24 00:10:55,399 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 3.3333333333333335) internal successors, (20), 5 states have internal predecessors, (20), 3 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) Word has length 70 [2024-10-24 00:10:55,400 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:10:55,402 INFO L225 Difference]: With dead ends: 119 [2024-10-24 00:10:55,403 INFO L226 Difference]: Without dead ends: 116 [2024-10-24 00:10:55,403 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 75 GetRequests, 67 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2024-10-24 00:10:55,404 INFO L432 NwaCegarLoop]: 47 mSDtfsCounter, 7 mSDsluCounter, 143 mSDsCounter, 0 mSdLazyCounter, 72 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 190 SdHoareTripleChecker+Invalid, 74 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 72 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-24 00:10:55,405 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 190 Invalid, 74 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 72 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-24 00:10:55,406 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 116 states. [2024-10-24 00:10:55,441 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 116 to 113. [2024-10-24 00:10:55,442 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 113 states, 60 states have (on average 1.2166666666666666) internal successors, (73), 62 states have internal predecessors, (73), 45 states have call successors, (45), 7 states have call predecessors, (45), 7 states have return successors, (43), 43 states have call predecessors, (43), 43 states have call successors, (43) [2024-10-24 00:10:55,444 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 113 states to 113 states and 161 transitions. [2024-10-24 00:10:55,444 INFO L78 Accepts]: Start accepts. Automaton has 113 states and 161 transitions. Word has length 70 [2024-10-24 00:10:55,446 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:10:55,446 INFO L471 AbstractCegarLoop]: Abstraction has 113 states and 161 transitions. [2024-10-24 00:10:55,446 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 3.3333333333333335) internal successors, (20), 5 states have internal predecessors, (20), 3 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2024-10-24 00:10:55,447 INFO L276 IsEmpty]: Start isEmpty. Operand 113 states and 161 transitions. [2024-10-24 00:10:55,447 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2024-10-24 00:10:55,448 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:10:55,448 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 6, 6, 6, 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-10-24 00:10:55,468 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-10-24 00:10:55,648 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:10:55,649 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:10:55,649 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:10:55,650 INFO L85 PathProgramCache]: Analyzing trace with hash 1519552206, now seen corresponding path program 2 times [2024-10-24 00:10:55,650 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:10:55,650 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2117329900] [2024-10-24 00:10:55,650 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:10:55,650 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:10:55,677 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:10:55,679 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2113463596] [2024-10-24 00:10:55,679 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-24 00:10:55,679 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:10:55,679 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:10:55,682 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-10-24 00:10:55,684 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-10-24 00:10:55,743 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-24 00:10:55,744 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-24 00:10:55,749 INFO L255 TraceCheckSpWp]: Trace formula consists of 189 conjuncts, 21 conjuncts are in the unsatisfiable core [2024-10-24 00:10:55,754 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:10:55,955 INFO L134 CoverageAnalysis]: Checked inductivity of 138 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2024-10-24 00:10:55,956 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:10:55,999 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:10:55,999 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2117329900] [2024-10-24 00:10:55,999 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 00:10:56,000 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2113463596] [2024-10-24 00:10:56,000 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2113463596] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 00:10:56,000 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-24 00:10:56,000 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2024-10-24 00:10:56,000 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [540995861] [2024-10-24 00:10:56,000 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-24 00:10:56,000 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-10-24 00:10:56,000 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:10:56,001 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-10-24 00:10:56,001 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2024-10-24 00:10:56,001 INFO L87 Difference]: Start difference. First operand 113 states and 161 transitions. Second operand has 7 states, 7 states have (on average 2.857142857142857) internal successors, (20), 6 states have internal predecessors, (20), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-10-24 00:10:56,156 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:10:56,157 INFO L93 Difference]: Finished difference Result 125 states and 171 transitions. [2024-10-24 00:10:56,157 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-10-24 00:10:56,158 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.857142857142857) internal successors, (20), 6 states have internal predecessors, (20), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 75 [2024-10-24 00:10:56,159 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:10:56,160 INFO L225 Difference]: With dead ends: 125 [2024-10-24 00:10:56,160 INFO L226 Difference]: Without dead ends: 123 [2024-10-24 00:10:56,160 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 71 SyntacticMatches, 2 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2024-10-24 00:10:56,162 INFO L432 NwaCegarLoop]: 41 mSDtfsCounter, 12 mSDsluCounter, 166 mSDsCounter, 0 mSdLazyCounter, 99 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 207 SdHoareTripleChecker+Invalid, 106 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 99 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-24 00:10:56,163 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 207 Invalid, 106 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 99 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-24 00:10:56,164 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 123 states. [2024-10-24 00:10:56,196 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 123 to 121. [2024-10-24 00:10:56,197 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 121 states, 66 states have (on average 1.196969696969697) internal successors, (79), 68 states have internal predecessors, (79), 45 states have call successors, (45), 9 states have call predecessors, (45), 9 states have return successors, (43), 43 states have call predecessors, (43), 43 states have call successors, (43) [2024-10-24 00:10:56,198 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 121 states to 121 states and 167 transitions. [2024-10-24 00:10:56,198 INFO L78 Accepts]: Start accepts. Automaton has 121 states and 167 transitions. Word has length 75 [2024-10-24 00:10:56,199 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:10:56,199 INFO L471 AbstractCegarLoop]: Abstraction has 121 states and 167 transitions. [2024-10-24 00:10:56,199 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.857142857142857) internal successors, (20), 6 states have internal predecessors, (20), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-10-24 00:10:56,199 INFO L276 IsEmpty]: Start isEmpty. Operand 121 states and 167 transitions. [2024-10-24 00:10:56,200 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 81 [2024-10-24 00:10:56,200 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:10:56,201 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 6, 6, 6, 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] [2024-10-24 00:10:56,218 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-10-24 00:10:56,404 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2024-10-24 00:10:56,405 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:10:56,405 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:10:56,405 INFO L85 PathProgramCache]: Analyzing trace with hash -1881497901, now seen corresponding path program 3 times [2024-10-24 00:10:56,406 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:10:56,406 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [958714758] [2024-10-24 00:10:56,406 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:10:56,406 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:10:56,427 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:10:56,428 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [623548598] [2024-10-24 00:10:56,428 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-10-24 00:10:56,428 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:10:56,428 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:10:56,430 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-10-24 00:10:56,431 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-10-24 00:10:56,497 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-10-24 00:10:56,498 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-24 00:10:56,499 INFO L255 TraceCheckSpWp]: Trace formula consists of 142 conjuncts, 43 conjuncts are in the unsatisfiable core [2024-10-24 00:10:56,502 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:10:58,025 INFO L134 CoverageAnalysis]: Checked inductivity of 165 backedges. 43 proven. 20 refuted. 0 times theorem prover too weak. 102 trivial. 0 not checked. [2024-10-24 00:10:58,025 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:10:58,291 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:10:58,292 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [958714758] [2024-10-24 00:10:58,292 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 00:10:58,292 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [623548598] [2024-10-24 00:10:58,292 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [623548598] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 00:10:58,292 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-24 00:10:58,292 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2024-10-24 00:10:58,292 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [708514130] [2024-10-24 00:10:58,293 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-24 00:10:58,294 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-10-24 00:10:58,294 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:10:58,294 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-10-24 00:10:58,295 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=56, Invalid=286, Unknown=0, NotChecked=0, Total=342 [2024-10-24 00:10:58,295 INFO L87 Difference]: Start difference. First operand 121 states and 167 transitions. Second operand has 16 states, 14 states have (on average 1.8571428571428572) internal successors, (26), 14 states have internal predecessors, (26), 6 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (13), 6 states have call predecessors, (13), 5 states have call successors, (13) [2024-10-24 00:10:59,193 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:10:59,193 INFO L93 Difference]: Finished difference Result 133 states and 177 transitions. [2024-10-24 00:10:59,193 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-10-24 00:10:59,194 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 14 states have (on average 1.8571428571428572) internal successors, (26), 14 states have internal predecessors, (26), 6 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (13), 6 states have call predecessors, (13), 5 states have call successors, (13) Word has length 80 [2024-10-24 00:10:59,194 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:10:59,195 INFO L225 Difference]: With dead ends: 133 [2024-10-24 00:10:59,195 INFO L226 Difference]: Without dead ends: 131 [2024-10-24 00:10:59,196 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 87 GetRequests, 67 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 76 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=79, Invalid=383, Unknown=0, NotChecked=0, Total=462 [2024-10-24 00:10:59,196 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 38 mSDsluCounter, 212 mSDsCounter, 0 mSdLazyCounter, 384 mSolverCounterSat, 20 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 50 SdHoareTripleChecker+Valid, 242 SdHoareTripleChecker+Invalid, 404 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 20 IncrementalHoareTripleChecker+Valid, 384 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2024-10-24 00:10:59,197 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [50 Valid, 242 Invalid, 404 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [20 Valid, 384 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2024-10-24 00:10:59,197 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 131 states. [2024-10-24 00:10:59,221 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 131 to 129. [2024-10-24 00:10:59,222 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 129 states, 72 states have (on average 1.1805555555555556) internal successors, (85), 74 states have internal predecessors, (85), 45 states have call successors, (45), 11 states have call predecessors, (45), 11 states have return successors, (43), 43 states have call predecessors, (43), 43 states have call successors, (43) [2024-10-24 00:10:59,223 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 129 states to 129 states and 173 transitions. [2024-10-24 00:10:59,223 INFO L78 Accepts]: Start accepts. Automaton has 129 states and 173 transitions. Word has length 80 [2024-10-24 00:10:59,223 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:10:59,223 INFO L471 AbstractCegarLoop]: Abstraction has 129 states and 173 transitions. [2024-10-24 00:10:59,224 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 14 states have (on average 1.8571428571428572) internal successors, (26), 14 states have internal predecessors, (26), 6 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (13), 6 states have call predecessors, (13), 5 states have call successors, (13) [2024-10-24 00:10:59,224 INFO L276 IsEmpty]: Start isEmpty. Operand 129 states and 173 transitions. [2024-10-24 00:10:59,225 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2024-10-24 00:10:59,225 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:10:59,225 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 6, 6, 6, 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, 1] [2024-10-24 00:10:59,244 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-10-24 00:10:59,425 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-10-24 00:10:59,426 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:10:59,426 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:10:59,426 INFO L85 PathProgramCache]: Analyzing trace with hash 1305329662, now seen corresponding path program 1 times [2024-10-24 00:10:59,426 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:10:59,427 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [997494289] [2024-10-24 00:10:59,427 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:10:59,427 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:10:59,448 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:10:59,451 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1052750382] [2024-10-24 00:10:59,451 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:10:59,451 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:10:59,451 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:10:59,453 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-10-24 00:10:59,454 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-10-24 00:10:59,521 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:10:59,523 INFO L255 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 41 conjuncts are in the unsatisfiable core [2024-10-24 00:10:59,525 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:11:00,056 INFO L134 CoverageAnalysis]: Checked inductivity of 196 backedges. 22 proven. 17 refuted. 0 times theorem prover too weak. 157 trivial. 0 not checked. [2024-10-24 00:11:00,057 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:11:00,959 INFO L134 CoverageAnalysis]: Checked inductivity of 196 backedges. 16 proven. 8 refuted. 0 times theorem prover too weak. 172 trivial. 0 not checked. [2024-10-24 00:11:00,960 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:11:00,960 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [997494289] [2024-10-24 00:11:00,960 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 00:11:00,960 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1052750382] [2024-10-24 00:11:00,960 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1052750382] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-24 00:11:00,960 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-24 00:11:00,960 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 21 [2024-10-24 00:11:00,961 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [738908595] [2024-10-24 00:11:00,961 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-24 00:11:00,961 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-10-24 00:11:00,961 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:11:00,962 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-10-24 00:11:00,962 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=356, Unknown=0, NotChecked=0, Total=420 [2024-10-24 00:11:00,962 INFO L87 Difference]: Start difference. First operand 129 states and 173 transitions. Second operand has 21 states, 19 states have (on average 1.894736842105263) internal successors, (36), 18 states have internal predecessors, (36), 10 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-10-24 00:11:03,777 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:11:03,778 INFO L93 Difference]: Finished difference Result 229 states and 336 transitions. [2024-10-24 00:11:03,778 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2024-10-24 00:11:03,778 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 19 states have (on average 1.894736842105263) internal successors, (36), 18 states have internal predecessors, (36), 10 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 86 [2024-10-24 00:11:03,778 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:11:03,781 INFO L225 Difference]: With dead ends: 229 [2024-10-24 00:11:03,781 INFO L226 Difference]: Without dead ends: 225 [2024-10-24 00:11:03,782 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 187 GetRequests, 151 SyntacticMatches, 0 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 206 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=255, Invalid=1151, Unknown=0, NotChecked=0, Total=1406 [2024-10-24 00:11:03,783 INFO L432 NwaCegarLoop]: 44 mSDtfsCounter, 74 mSDsluCounter, 450 mSDsCounter, 0 mSdLazyCounter, 545 mSolverCounterSat, 108 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 79 SdHoareTripleChecker+Valid, 494 SdHoareTripleChecker+Invalid, 653 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 108 IncrementalHoareTripleChecker+Valid, 545 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.8s IncrementalHoareTripleChecker+Time [2024-10-24 00:11:03,783 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [79 Valid, 494 Invalid, 653 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [108 Valid, 545 Invalid, 0 Unknown, 0 Unchecked, 1.8s Time] [2024-10-24 00:11:03,783 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 225 states. [2024-10-24 00:11:03,855 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 225 to 222. [2024-10-24 00:11:03,856 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 222 states, 114 states have (on average 1.236842105263158) internal successors, (141), 117 states have internal predecessors, (141), 94 states have call successors, (94), 13 states have call predecessors, (94), 13 states have return successors, (92), 91 states have call predecessors, (92), 92 states have call successors, (92) [2024-10-24 00:11:03,858 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 222 states to 222 states and 327 transitions. [2024-10-24 00:11:03,858 INFO L78 Accepts]: Start accepts. Automaton has 222 states and 327 transitions. Word has length 86 [2024-10-24 00:11:03,859 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:11:03,859 INFO L471 AbstractCegarLoop]: Abstraction has 222 states and 327 transitions. [2024-10-24 00:11:03,859 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 19 states have (on average 1.894736842105263) internal successors, (36), 18 states have internal predecessors, (36), 10 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-10-24 00:11:03,859 INFO L276 IsEmpty]: Start isEmpty. Operand 222 states and 327 transitions. [2024-10-24 00:11:03,860 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 96 [2024-10-24 00:11:03,860 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:11:03,860 INFO L215 NwaCegarLoop]: trace histogram [10, 9, 9, 6, 6, 6, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:11:03,875 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2024-10-24 00:11:04,064 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2024-10-24 00:11:04,065 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:11:04,065 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:11:04,065 INFO L85 PathProgramCache]: Analyzing trace with hash 1470837899, now seen corresponding path program 4 times [2024-10-24 00:11:04,065 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:11:04,065 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [432073638] [2024-10-24 00:11:04,065 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:04,066 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:11:04,080 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:04,160 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-24 00:11:04,161 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:04,163 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-24 00:11:04,166 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:04,167 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-24 00:11:04,168 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:04,169 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-24 00:11:04,170 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:04,171 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-10-24 00:11:04,172 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:04,173 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2024-10-24 00:11:04,173 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:04,174 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2024-10-24 00:11:04,175 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:04,177 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 41 [2024-10-24 00:11:04,178 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:04,179 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 46 [2024-10-24 00:11:04,179 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:04,180 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 51 [2024-10-24 00:11:04,181 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:04,182 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 61 [2024-10-24 00:11:04,183 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:04,186 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 66 [2024-10-24 00:11:04,187 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:04,189 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 71 [2024-10-24 00:11:04,190 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:04,192 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 76 [2024-10-24 00:11:04,193 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:04,196 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 86 [2024-10-24 00:11:04,197 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:04,199 INFO L134 CoverageAnalysis]: Checked inductivity of 241 backedges. 37 proven. 0 refuted. 0 times theorem prover too weak. 204 trivial. 0 not checked. [2024-10-24 00:11:04,199 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:11:04,199 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [432073638] [2024-10-24 00:11:04,199 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [432073638] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 00:11:04,199 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-24 00:11:04,199 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-24 00:11:04,199 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1539885896] [2024-10-24 00:11:04,200 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 00:11:04,200 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-24 00:11:04,200 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:11:04,200 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-24 00:11:04,201 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-24 00:11:04,201 INFO L87 Difference]: Start difference. First operand 222 states and 327 transitions. Second operand has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 3 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (15), 3 states have call predecessors, (15), 3 states have call successors, (15) [2024-10-24 00:11:04,297 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:11:04,297 INFO L93 Difference]: Finished difference Result 275 states and 403 transitions. [2024-10-24 00:11:04,298 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-24 00:11:04,298 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 3 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (15), 3 states have call predecessors, (15), 3 states have call successors, (15) Word has length 95 [2024-10-24 00:11:04,298 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:11:04,300 INFO L225 Difference]: With dead ends: 275 [2024-10-24 00:11:04,300 INFO L226 Difference]: Without dead ends: 201 [2024-10-24 00:11:04,301 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 37 GetRequests, 32 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-10-24 00:11:04,301 INFO L432 NwaCegarLoop]: 48 mSDtfsCounter, 6 mSDsluCounter, 118 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 166 SdHoareTripleChecker+Invalid, 44 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-24 00:11:04,302 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 166 Invalid, 44 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-24 00:11:04,302 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 201 states. [2024-10-24 00:11:04,364 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 201 to 189. [2024-10-24 00:11:04,365 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 189 states, 97 states have (on average 1.175257731958763) internal successors, (114), 100 states have internal predecessors, (114), 78 states have call successors, (78), 13 states have call predecessors, (78), 13 states have return successors, (76), 75 states have call predecessors, (76), 76 states have call successors, (76) [2024-10-24 00:11:04,366 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 189 states to 189 states and 268 transitions. [2024-10-24 00:11:04,367 INFO L78 Accepts]: Start accepts. Automaton has 189 states and 268 transitions. Word has length 95 [2024-10-24 00:11:04,367 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:11:04,367 INFO L471 AbstractCegarLoop]: Abstraction has 189 states and 268 transitions. [2024-10-24 00:11:04,367 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 3 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (15), 3 states have call predecessors, (15), 3 states have call successors, (15) [2024-10-24 00:11:04,368 INFO L276 IsEmpty]: Start isEmpty. Operand 189 states and 268 transitions. [2024-10-24 00:11:04,368 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 103 [2024-10-24 00:11:04,369 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:11:04,369 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 6, 6, 6, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:11:04,369 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11 [2024-10-24 00:11:04,369 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:11:04,369 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:11:04,370 INFO L85 PathProgramCache]: Analyzing trace with hash 1556724626, now seen corresponding path program 1 times [2024-10-24 00:11:04,370 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:11:04,370 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [733512041] [2024-10-24 00:11:04,370 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:04,370 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:11:04,391 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:11:04,392 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2046915090] [2024-10-24 00:11:04,392 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:04,392 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:11:04,393 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:11:04,394 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-10-24 00:11:04,396 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-10-24 00:11:04,481 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:04,484 INFO L255 TraceCheckSpWp]: Trace formula consists of 240 conjuncts, 52 conjuncts are in the unsatisfiable core [2024-10-24 00:11:04,486 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:11:05,298 INFO L134 CoverageAnalysis]: Checked inductivity of 320 backedges. 74 proven. 35 refuted. 0 times theorem prover too weak. 211 trivial. 0 not checked. [2024-10-24 00:11:05,298 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:11:07,121 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:11:07,122 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [733512041] [2024-10-24 00:11:07,122 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 00:11:07,122 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2046915090] [2024-10-24 00:11:07,122 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2046915090] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 00:11:07,122 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-24 00:11:07,122 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2024-10-24 00:11:07,122 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1179679859] [2024-10-24 00:11:07,122 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-24 00:11:07,123 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-10-24 00:11:07,123 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:11:07,123 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-10-24 00:11:07,124 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=90, Invalid=462, Unknown=0, NotChecked=0, Total=552 [2024-10-24 00:11:07,124 INFO L87 Difference]: Start difference. First operand 189 states and 268 transitions. Second operand has 16 states, 16 states have (on average 1.75) internal successors, (28), 13 states have internal predecessors, (28), 6 states have call successors, (18), 2 states have call predecessors, (18), 3 states have return successors, (17), 7 states have call predecessors, (17), 6 states have call successors, (17) [2024-10-24 00:11:07,721 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:11:07,721 INFO L93 Difference]: Finished difference Result 201 states and 278 transitions. [2024-10-24 00:11:07,722 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-10-24 00:11:07,723 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 1.75) internal successors, (28), 13 states have internal predecessors, (28), 6 states have call successors, (18), 2 states have call predecessors, (18), 3 states have return successors, (17), 7 states have call predecessors, (17), 6 states have call successors, (17) Word has length 102 [2024-10-24 00:11:07,723 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:11:07,724 INFO L225 Difference]: With dead ends: 201 [2024-10-24 00:11:07,724 INFO L226 Difference]: Without dead ends: 199 [2024-10-24 00:11:07,725 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 131 GetRequests, 104 SyntacticMatches, 0 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 140 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=140, Invalid=672, Unknown=0, NotChecked=0, Total=812 [2024-10-24 00:11:07,725 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 28 mSDsluCounter, 163 mSDsCounter, 0 mSdLazyCounter, 409 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 38 SdHoareTripleChecker+Valid, 194 SdHoareTripleChecker+Invalid, 435 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 409 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-10-24 00:11:07,725 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [38 Valid, 194 Invalid, 435 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 409 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-10-24 00:11:07,726 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 199 states. [2024-10-24 00:11:07,779 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 199 to 197. [2024-10-24 00:11:07,779 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 197 states, 103 states have (on average 1.1650485436893203) internal successors, (120), 106 states have internal predecessors, (120), 78 states have call successors, (78), 15 states have call predecessors, (78), 15 states have return successors, (76), 75 states have call predecessors, (76), 76 states have call successors, (76) [2024-10-24 00:11:07,780 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 197 states to 197 states and 274 transitions. [2024-10-24 00:11:07,781 INFO L78 Accepts]: Start accepts. Automaton has 197 states and 274 transitions. Word has length 102 [2024-10-24 00:11:07,781 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:11:07,781 INFO L471 AbstractCegarLoop]: Abstraction has 197 states and 274 transitions. [2024-10-24 00:11:07,781 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 1.75) internal successors, (28), 13 states have internal predecessors, (28), 6 states have call successors, (18), 2 states have call predecessors, (18), 3 states have return successors, (17), 7 states have call predecessors, (17), 6 states have call successors, (17) [2024-10-24 00:11:07,781 INFO L276 IsEmpty]: Start isEmpty. Operand 197 states and 274 transitions. [2024-10-24 00:11:07,783 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 117 [2024-10-24 00:11:07,783 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:11:07,783 INFO L215 NwaCegarLoop]: trace histogram [14, 13, 13, 6, 6, 6, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:11:07,799 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2024-10-24 00:11:07,987 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,SelfDestructingSolverStorable12 [2024-10-24 00:11:07,988 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:11:07,988 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:11:07,988 INFO L85 PathProgramCache]: Analyzing trace with hash -1903041589, now seen corresponding path program 1 times [2024-10-24 00:11:07,988 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:11:07,988 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1023225809] [2024-10-24 00:11:07,988 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:07,988 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:11:08,006 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:08,104 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-24 00:11:08,105 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:08,106 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-24 00:11:08,107 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:08,108 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-24 00:11:08,108 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:08,109 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-24 00:11:08,110 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:08,111 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-10-24 00:11:08,111 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:08,112 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2024-10-24 00:11:08,113 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:08,114 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2024-10-24 00:11:08,114 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:08,115 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 41 [2024-10-24 00:11:08,116 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:08,117 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 46 [2024-10-24 00:11:08,117 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:08,118 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 51 [2024-10-24 00:11:08,119 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:08,120 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 61 [2024-10-24 00:11:08,121 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:08,123 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 66 [2024-10-24 00:11:08,124 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:08,126 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 71 [2024-10-24 00:11:08,127 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:08,128 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 76 [2024-10-24 00:11:08,130 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:08,132 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 83 [2024-10-24 00:11:08,132 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:08,134 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 88 [2024-10-24 00:11:08,135 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:08,137 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 93 [2024-10-24 00:11:08,137 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:08,139 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 98 [2024-10-24 00:11:08,141 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:08,143 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 107 [2024-10-24 00:11:08,144 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:08,145 INFO L134 CoverageAnalysis]: Checked inductivity of 423 backedges. 42 proven. 9 refuted. 0 times theorem prover too weak. 372 trivial. 0 not checked. [2024-10-24 00:11:08,145 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:11:08,145 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1023225809] [2024-10-24 00:11:08,145 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1023225809] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 00:11:08,146 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1413541603] [2024-10-24 00:11:08,146 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:08,146 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:11:08,146 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:11:08,148 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-10-24 00:11:08,158 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-10-24 00:11:08,221 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:08,222 INFO L255 TraceCheckSpWp]: Trace formula consists of 274 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-24 00:11:08,224 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:11:08,259 INFO L134 CoverageAnalysis]: Checked inductivity of 423 backedges. 88 proven. 9 refuted. 0 times theorem prover too weak. 326 trivial. 0 not checked. [2024-10-24 00:11:08,259 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:11:08,348 INFO L134 CoverageAnalysis]: Checked inductivity of 423 backedges. 42 proven. 9 refuted. 0 times theorem prover too weak. 372 trivial. 0 not checked. [2024-10-24 00:11:08,349 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1413541603] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-24 00:11:08,349 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-24 00:11:08,349 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 7 [2024-10-24 00:11:08,349 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [14557113] [2024-10-24 00:11:08,349 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-24 00:11:08,349 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-10-24 00:11:08,350 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:11:08,350 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-10-24 00:11:08,350 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2024-10-24 00:11:08,350 INFO L87 Difference]: Start difference. First operand 197 states and 274 transitions. Second operand has 7 states, 7 states have (on average 4.0) internal successors, (28), 7 states have internal predecessors, (28), 4 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 4 states have call predecessors, (20), 4 states have call successors, (20) [2024-10-24 00:11:08,628 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:11:08,628 INFO L93 Difference]: Finished difference Result 223 states and 313 transitions. [2024-10-24 00:11:08,629 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-10-24 00:11:08,629 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 4.0) internal successors, (28), 7 states have internal predecessors, (28), 4 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 4 states have call predecessors, (20), 4 states have call successors, (20) Word has length 116 [2024-10-24 00:11:08,629 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:11:08,631 INFO L225 Difference]: With dead ends: 223 [2024-10-24 00:11:08,631 INFO L226 Difference]: Without dead ends: 211 [2024-10-24 00:11:08,631 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 286 GetRequests, 267 SyntacticMatches, 6 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=62, Invalid=148, Unknown=0, NotChecked=0, Total=210 [2024-10-24 00:11:08,632 INFO L432 NwaCegarLoop]: 67 mSDtfsCounter, 17 mSDsluCounter, 251 mSDsCounter, 0 mSdLazyCounter, 99 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 318 SdHoareTripleChecker+Invalid, 121 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 99 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-24 00:11:08,632 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 318 Invalid, 121 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 99 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-24 00:11:08,633 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 211 states. [2024-10-24 00:11:08,687 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 211 to 192. [2024-10-24 00:11:08,688 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 192 states, 100 states have (on average 1.16) internal successors, (116), 102 states have internal predecessors, (116), 77 states have call successors, (77), 14 states have call predecessors, (77), 14 states have return successors, (75), 75 states have call predecessors, (75), 75 states have call successors, (75) [2024-10-24 00:11:08,689 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 192 states to 192 states and 268 transitions. [2024-10-24 00:11:08,689 INFO L78 Accepts]: Start accepts. Automaton has 192 states and 268 transitions. Word has length 116 [2024-10-24 00:11:08,690 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:11:08,690 INFO L471 AbstractCegarLoop]: Abstraction has 192 states and 268 transitions. [2024-10-24 00:11:08,690 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 4.0) internal successors, (28), 7 states have internal predecessors, (28), 4 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 4 states have call predecessors, (20), 4 states have call successors, (20) [2024-10-24 00:11:08,690 INFO L276 IsEmpty]: Start isEmpty. Operand 192 states and 268 transitions. [2024-10-24 00:11:08,691 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 118 [2024-10-24 00:11:08,691 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:11:08,691 INFO L215 NwaCegarLoop]: trace histogram [14, 13, 13, 6, 6, 6, 4, 4, 4, 4, 3, 3, 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] [2024-10-24 00:11:08,709 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2024-10-24 00:11:08,892 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,SelfDestructingSolverStorable13 [2024-10-24 00:11:08,892 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:11:08,893 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:11:08,893 INFO L85 PathProgramCache]: Analyzing trace with hash -956526070, now seen corresponding path program 2 times [2024-10-24 00:11:08,893 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:11:08,893 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1272620232] [2024-10-24 00:11:08,893 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:08,893 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:11:08,929 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:11:08,933 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1047452991] [2024-10-24 00:11:08,933 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-24 00:11:08,933 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:11:08,933 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:11:08,935 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-10-24 00:11:08,936 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-10-24 00:11:09,016 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-24 00:11:09,016 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-24 00:11:09,018 INFO L255 TraceCheckSpWp]: Trace formula consists of 278 conjuncts, 50 conjuncts are in the unsatisfiable core [2024-10-24 00:11:09,021 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:11:09,542 INFO L134 CoverageAnalysis]: Checked inductivity of 432 backedges. 61 proven. 50 refuted. 0 times theorem prover too weak. 321 trivial. 0 not checked. [2024-10-24 00:11:09,543 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:11:09,848 INFO L134 CoverageAnalysis]: Checked inductivity of 432 backedges. 73 proven. 7 refuted. 0 times theorem prover too weak. 352 trivial. 0 not checked. [2024-10-24 00:11:09,849 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:11:09,849 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1272620232] [2024-10-24 00:11:09,849 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 00:11:09,849 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1047452991] [2024-10-24 00:11:09,850 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1047452991] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-24 00:11:09,850 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-24 00:11:09,850 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 8] total 22 [2024-10-24 00:11:09,850 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1113446770] [2024-10-24 00:11:09,850 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-24 00:11:09,851 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-10-24 00:11:09,851 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:11:09,851 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-10-24 00:11:09,852 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=396, Unknown=0, NotChecked=0, Total=462 [2024-10-24 00:11:09,852 INFO L87 Difference]: Start difference. First operand 192 states and 268 transitions. Second operand has 22 states, 22 states have (on average 2.227272727272727) internal successors, (49), 19 states have internal predecessors, (49), 9 states have call successors, (30), 3 states have call predecessors, (30), 3 states have return successors, (30), 9 states have call predecessors, (30), 9 states have call successors, (30) [2024-10-24 00:11:12,113 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:11:12,113 INFO L93 Difference]: Finished difference Result 226 states and 314 transitions. [2024-10-24 00:11:12,114 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2024-10-24 00:11:12,114 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 2.227272727272727) internal successors, (49), 19 states have internal predecessors, (49), 9 states have call successors, (30), 3 states have call predecessors, (30), 3 states have return successors, (30), 9 states have call predecessors, (30), 9 states have call successors, (30) Word has length 117 [2024-10-24 00:11:12,114 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:11:12,116 INFO L225 Difference]: With dead ends: 226 [2024-10-24 00:11:12,116 INFO L226 Difference]: Without dead ends: 223 [2024-10-24 00:11:12,117 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 244 GetRequests, 213 SyntacticMatches, 0 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 171 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=173, Invalid=883, Unknown=0, NotChecked=0, Total=1056 [2024-10-24 00:11:12,117 INFO L432 NwaCegarLoop]: 41 mSDtfsCounter, 59 mSDsluCounter, 385 mSDsCounter, 0 mSdLazyCounter, 588 mSolverCounterSat, 101 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 61 SdHoareTripleChecker+Valid, 426 SdHoareTripleChecker+Invalid, 689 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 101 IncrementalHoareTripleChecker+Valid, 588 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.2s IncrementalHoareTripleChecker+Time [2024-10-24 00:11:12,118 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [61 Valid, 426 Invalid, 689 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [101 Valid, 588 Invalid, 0 Unknown, 0 Unchecked, 1.2s Time] [2024-10-24 00:11:12,118 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 223 states. [2024-10-24 00:11:12,194 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 223 to 165. [2024-10-24 00:11:12,194 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 165 states, 88 states have (on average 1.1590909090909092) internal successors, (102), 89 states have internal predecessors, (102), 63 states have call successors, (63), 13 states have call predecessors, (63), 13 states have return successors, (62), 62 states have call predecessors, (62), 62 states have call successors, (62) [2024-10-24 00:11:12,196 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 165 states to 165 states and 227 transitions. [2024-10-24 00:11:12,196 INFO L78 Accepts]: Start accepts. Automaton has 165 states and 227 transitions. Word has length 117 [2024-10-24 00:11:12,197 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:11:12,197 INFO L471 AbstractCegarLoop]: Abstraction has 165 states and 227 transitions. [2024-10-24 00:11:12,197 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 2.227272727272727) internal successors, (49), 19 states have internal predecessors, (49), 9 states have call successors, (30), 3 states have call predecessors, (30), 3 states have return successors, (30), 9 states have call predecessors, (30), 9 states have call successors, (30) [2024-10-24 00:11:12,197 INFO L276 IsEmpty]: Start isEmpty. Operand 165 states and 227 transitions. [2024-10-24 00:11:12,198 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 120 [2024-10-24 00:11:12,198 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:11:12,199 INFO L215 NwaCegarLoop]: trace histogram [15, 14, 14, 6, 6, 6, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:11:12,218 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2024-10-24 00:11:12,399 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2024-10-24 00:11:12,400 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:11:12,400 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:11:12,400 INFO L85 PathProgramCache]: Analyzing trace with hash 457852880, now seen corresponding path program 3 times [2024-10-24 00:11:12,400 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:11:12,400 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [124426541] [2024-10-24 00:11:12,400 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:12,400 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:11:12,430 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:11:12,431 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1352673] [2024-10-24 00:11:12,431 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-10-24 00:11:12,431 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:11:12,431 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:11:12,433 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-24 00:11:12,434 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2024-10-24 00:11:12,509 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2024-10-24 00:11:12,510 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-24 00:11:12,519 INFO L255 TraceCheckSpWp]: Trace formula consists of 199 conjuncts, 45 conjuncts are in the unsatisfiable core [2024-10-24 00:11:12,522 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:11:12,994 INFO L134 CoverageAnalysis]: Checked inductivity of 484 backedges. 60 proven. 39 refuted. 0 times theorem prover too weak. 385 trivial. 0 not checked. [2024-10-24 00:11:12,994 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:11:15,688 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:11:15,688 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [124426541] [2024-10-24 00:11:15,688 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 00:11:15,688 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1352673] [2024-10-24 00:11:15,688 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1352673] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 00:11:15,688 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-24 00:11:15,688 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2024-10-24 00:11:15,688 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [851177899] [2024-10-24 00:11:15,688 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-24 00:11:15,689 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-10-24 00:11:15,689 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:11:15,689 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-10-24 00:11:15,689 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=194, Unknown=0, NotChecked=0, Total=240 [2024-10-24 00:11:15,690 INFO L87 Difference]: Start difference. First operand 165 states and 227 transitions. Second operand has 12 states, 12 states have (on average 2.25) internal successors, (27), 11 states have internal predecessors, (27), 6 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 7 states have call predecessors, (20), 6 states have call successors, (20) [2024-10-24 00:11:16,038 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:11:16,039 INFO L93 Difference]: Finished difference Result 203 states and 276 transitions. [2024-10-24 00:11:16,039 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-10-24 00:11:16,040 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.25) internal successors, (27), 11 states have internal predecessors, (27), 6 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 7 states have call predecessors, (20), 6 states have call successors, (20) Word has length 119 [2024-10-24 00:11:16,040 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:11:16,042 INFO L225 Difference]: With dead ends: 203 [2024-10-24 00:11:16,042 INFO L226 Difference]: Without dead ends: 201 [2024-10-24 00:11:16,042 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 142 GetRequests, 124 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=75, Invalid=305, Unknown=0, NotChecked=0, Total=380 [2024-10-24 00:11:16,043 INFO L432 NwaCegarLoop]: 43 mSDtfsCounter, 22 mSDsluCounter, 316 mSDsCounter, 0 mSdLazyCounter, 354 mSolverCounterSat, 35 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 359 SdHoareTripleChecker+Invalid, 389 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 35 IncrementalHoareTripleChecker+Valid, 354 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-10-24 00:11:16,045 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 359 Invalid, 389 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [35 Valid, 354 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-10-24 00:11:16,046 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 201 states. [2024-10-24 00:11:16,104 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 201 to 198. [2024-10-24 00:11:16,105 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 198 states, 106 states have (on average 1.150943396226415) internal successors, (122), 107 states have internal predecessors, (122), 75 states have call successors, (75), 16 states have call predecessors, (75), 16 states have return successors, (74), 74 states have call predecessors, (74), 74 states have call successors, (74) [2024-10-24 00:11:16,106 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 198 states to 198 states and 271 transitions. [2024-10-24 00:11:16,108 INFO L78 Accepts]: Start accepts. Automaton has 198 states and 271 transitions. Word has length 119 [2024-10-24 00:11:16,108 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:11:16,108 INFO L471 AbstractCegarLoop]: Abstraction has 198 states and 271 transitions. [2024-10-24 00:11:16,108 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 2.25) internal successors, (27), 11 states have internal predecessors, (27), 6 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 7 states have call predecessors, (20), 6 states have call successors, (20) [2024-10-24 00:11:16,108 INFO L276 IsEmpty]: Start isEmpty. Operand 198 states and 271 transitions. [2024-10-24 00:11:16,110 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 123 [2024-10-24 00:11:16,110 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:11:16,110 INFO L215 NwaCegarLoop]: trace histogram [15, 14, 14, 6, 6, 6, 4, 4, 4, 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] [2024-10-24 00:11:16,129 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2024-10-24 00:11:16,314 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:11:16,315 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:11:16,315 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:11:16,315 INFO L85 PathProgramCache]: Analyzing trace with hash -2126175913, now seen corresponding path program 4 times [2024-10-24 00:11:16,315 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:11:16,315 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2121941103] [2024-10-24 00:11:16,315 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:16,315 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:11:16,339 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:11:16,340 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1356488723] [2024-10-24 00:11:16,341 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-10-24 00:11:16,341 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:11:16,341 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:11:16,343 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-24 00:11:16,353 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2024-10-24 00:11:16,434 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-10-24 00:11:16,434 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-24 00:11:16,436 INFO L255 TraceCheckSpWp]: Trace formula consists of 248 conjuncts, 45 conjuncts are in the unsatisfiable core [2024-10-24 00:11:16,439 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:11:17,301 INFO L134 CoverageAnalysis]: Checked inductivity of 489 backedges. 57 proven. 47 refuted. 0 times theorem prover too weak. 385 trivial. 0 not checked. [2024-10-24 00:11:17,301 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:11:19,253 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:11:19,253 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2121941103] [2024-10-24 00:11:19,253 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 00:11:19,253 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1356488723] [2024-10-24 00:11:19,253 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1356488723] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 00:11:19,253 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-24 00:11:19,253 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2024-10-24 00:11:19,253 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [776342767] [2024-10-24 00:11:19,253 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-24 00:11:19,254 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-10-24 00:11:19,254 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:11:19,254 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-10-24 00:11:19,254 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=89, Invalid=463, Unknown=0, NotChecked=0, Total=552 [2024-10-24 00:11:19,255 INFO L87 Difference]: Start difference. First operand 198 states and 271 transitions. Second operand has 15 states, 15 states have (on average 2.0) internal successors, (30), 13 states have internal predecessors, (30), 7 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) [2024-10-24 00:11:20,140 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:11:20,141 INFO L93 Difference]: Finished difference Result 261 states and 358 transitions. [2024-10-24 00:11:20,141 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-10-24 00:11:20,141 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.0) internal successors, (30), 13 states have internal predecessors, (30), 7 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) Word has length 122 [2024-10-24 00:11:20,141 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:11:20,143 INFO L225 Difference]: With dead ends: 261 [2024-10-24 00:11:20,143 INFO L226 Difference]: Without dead ends: 259 [2024-10-24 00:11:20,144 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 195 GetRequests, 164 SyntacticMatches, 2 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 113 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=159, Invalid=771, Unknown=0, NotChecked=0, Total=930 [2024-10-24 00:11:20,145 INFO L432 NwaCegarLoop]: 46 mSDtfsCounter, 24 mSDsluCounter, 421 mSDsCounter, 0 mSdLazyCounter, 437 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 467 SdHoareTripleChecker+Invalid, 463 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 437 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-10-24 00:11:20,145 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 467 Invalid, 463 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 437 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-10-24 00:11:20,145 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 259 states. [2024-10-24 00:11:20,240 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 259 to 256. [2024-10-24 00:11:20,240 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 256 states, 136 states have (on average 1.1470588235294117) internal successors, (156), 137 states have internal predecessors, (156), 99 states have call successors, (99), 20 states have call predecessors, (99), 20 states have return successors, (98), 98 states have call predecessors, (98), 98 states have call successors, (98) [2024-10-24 00:11:20,242 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 256 states to 256 states and 353 transitions. [2024-10-24 00:11:20,242 INFO L78 Accepts]: Start accepts. Automaton has 256 states and 353 transitions. Word has length 122 [2024-10-24 00:11:20,242 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:11:20,243 INFO L471 AbstractCegarLoop]: Abstraction has 256 states and 353 transitions. [2024-10-24 00:11:20,243 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.0) internal successors, (30), 13 states have internal predecessors, (30), 7 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) [2024-10-24 00:11:20,243 INFO L276 IsEmpty]: Start isEmpty. Operand 256 states and 353 transitions. [2024-10-24 00:11:20,244 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 125 [2024-10-24 00:11:20,244 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:11:20,244 INFO L215 NwaCegarLoop]: trace histogram [16, 15, 15, 6, 6, 6, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:11:20,266 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Ended with exit code 0 [2024-10-24 00:11:20,445 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2024-10-24 00:11:20,445 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:11:20,446 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:11:20,446 INFO L85 PathProgramCache]: Analyzing trace with hash 71118609, now seen corresponding path program 5 times [2024-10-24 00:11:20,446 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:11:20,446 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [137376255] [2024-10-24 00:11:20,446 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:20,446 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:11:20,467 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:11:20,468 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1532539547] [2024-10-24 00:11:20,468 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-10-24 00:11:20,468 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:11:20,469 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:11:20,471 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-24 00:11:20,474 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2024-10-24 00:11:20,609 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 7 check-sat command(s) [2024-10-24 00:11:20,609 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-24 00:11:20,610 INFO L255 TraceCheckSpWp]: Trace formula consists of 282 conjuncts, 44 conjuncts are in the unsatisfiable core [2024-10-24 00:11:20,613 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:11:21,677 INFO L134 CoverageAnalysis]: Checked inductivity of 545 backedges. 76 proven. 67 refuted. 0 times theorem prover too weak. 402 trivial. 0 not checked. [2024-10-24 00:11:21,678 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:11:22,231 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:11:22,231 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [137376255] [2024-10-24 00:11:22,231 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 00:11:22,231 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1532539547] [2024-10-24 00:11:22,231 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1532539547] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 00:11:22,232 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-24 00:11:22,232 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2024-10-24 00:11:22,232 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [124515638] [2024-10-24 00:11:22,232 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-24 00:11:22,233 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-10-24 00:11:22,233 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:11:22,234 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-10-24 00:11:22,234 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=255, Unknown=0, NotChecked=0, Total=306 [2024-10-24 00:11:22,234 INFO L87 Difference]: Start difference. First operand 256 states and 353 transitions. Second operand has 15 states, 14 states have (on average 1.9285714285714286) internal successors, (27), 12 states have internal predecessors, (27), 7 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (21), 8 states have call predecessors, (21), 6 states have call successors, (21) [2024-10-24 00:11:23,167 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:11:23,167 INFO L93 Difference]: Finished difference Result 264 states and 360 transitions. [2024-10-24 00:11:23,168 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-10-24 00:11:23,168 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 1.9285714285714286) internal successors, (27), 12 states have internal predecessors, (27), 7 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (21), 8 states have call predecessors, (21), 6 states have call successors, (21) Word has length 124 [2024-10-24 00:11:23,169 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:11:23,170 INFO L225 Difference]: With dead ends: 264 [2024-10-24 00:11:23,170 INFO L226 Difference]: Without dead ends: 262 [2024-10-24 00:11:23,171 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 133 GetRequests, 112 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 50 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=85, Invalid=421, Unknown=0, NotChecked=0, Total=506 [2024-10-24 00:11:23,171 INFO L432 NwaCegarLoop]: 49 mSDtfsCounter, 23 mSDsluCounter, 430 mSDsCounter, 0 mSdLazyCounter, 488 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 479 SdHoareTripleChecker+Invalid, 510 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 488 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2024-10-24 00:11:23,171 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [30 Valid, 479 Invalid, 510 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 488 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2024-10-24 00:11:23,172 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 262 states. [2024-10-24 00:11:23,258 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 262 to 260. [2024-10-24 00:11:23,259 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 260 states, 139 states have (on average 1.143884892086331) internal successors, (159), 140 states have internal predecessors, (159), 99 states have call successors, (99), 21 states have call predecessors, (99), 21 states have return successors, (98), 98 states have call predecessors, (98), 98 states have call successors, (98) [2024-10-24 00:11:23,260 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 260 states to 260 states and 356 transitions. [2024-10-24 00:11:23,260 INFO L78 Accepts]: Start accepts. Automaton has 260 states and 356 transitions. Word has length 124 [2024-10-24 00:11:23,260 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:11:23,261 INFO L471 AbstractCegarLoop]: Abstraction has 260 states and 356 transitions. [2024-10-24 00:11:23,261 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 14 states have (on average 1.9285714285714286) internal successors, (27), 12 states have internal predecessors, (27), 7 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (21), 8 states have call predecessors, (21), 6 states have call successors, (21) [2024-10-24 00:11:23,261 INFO L276 IsEmpty]: Start isEmpty. Operand 260 states and 356 transitions. [2024-10-24 00:11:23,261 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 128 [2024-10-24 00:11:23,262 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:11:23,262 INFO L215 NwaCegarLoop]: trace histogram [16, 15, 15, 6, 6, 6, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:11:23,268 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Ended with exit code 0 [2024-10-24 00:11:23,462 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2024-10-24 00:11:23,462 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:11:23,463 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:11:23,463 INFO L85 PathProgramCache]: Analyzing trace with hash 2088776170, now seen corresponding path program 6 times [2024-10-24 00:11:23,463 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:11:23,463 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1492609097] [2024-10-24 00:11:23,463 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:23,463 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:11:23,480 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:11:23,482 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [834978490] [2024-10-24 00:11:23,482 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2024-10-24 00:11:23,482 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:11:23,482 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:11:23,484 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-24 00:11:23,485 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2024-10-24 00:11:23,996 INFO L227 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) [2024-10-24 00:11:23,996 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-24 00:11:23,998 INFO L255 TraceCheckSpWp]: Trace formula consists of 251 conjuncts, 74 conjuncts are in the unsatisfiable core [2024-10-24 00:11:24,001 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:11:28,503 INFO L134 CoverageAnalysis]: Checked inductivity of 550 backedges. 134 proven. 68 refuted. 0 times theorem prover too weak. 348 trivial. 0 not checked. [2024-10-24 00:11:28,503 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:11:33,812 WARN L873 $PredicateComparison]: unable to prove that (or (not (= (+ (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~s~0#1|) (* |c_ULTIMATE.start_main_~x~0#1| |c_ULTIMATE.start_main_~q~0#1|) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~b~0#1|)) (+ (* |c_ULTIMATE.start_main_~xy~0#1| |c_ULTIMATE.start_main_~q~0#1|) (* |c_ULTIMATE.start_main_~yy~0#1| |c_ULTIMATE.start_main_~s~0#1|) |c_ULTIMATE.start_main_~b~0#1|))) (not (= (+ (* |c_ULTIMATE.start_main_~x~0#1| |c_ULTIMATE.start_main_~p~0#1|) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~r~0#1|)) (+ |c_ULTIMATE.start_main_~c~0#1| (* |c_ULTIMATE.start_main_~x~0#1| |c_ULTIMATE.start_main_~k~0#1| |c_ULTIMATE.start_main_~q~0#1|) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~s~0#1| |c_ULTIMATE.start_main_~k~0#1|)))) (= (+ (* |c_ULTIMATE.start_main_~yy~0#1| |c_ULTIMATE.start_main_~r~0#1|) (* |c_ULTIMATE.start_main_~xy~0#1| |c_ULTIMATE.start_main_~p~0#1|) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~s~0#1| |c_ULTIMATE.start_main_~k~0#1|) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~x~0#1| |c_ULTIMATE.start_main_~k~0#1| |c_ULTIMATE.start_main_~q~0#1|)) (+ (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~r~0#1|) (* |c_ULTIMATE.start_main_~xy~0#1| |c_ULTIMATE.start_main_~k~0#1| |c_ULTIMATE.start_main_~q~0#1|) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~x~0#1| |c_ULTIMATE.start_main_~p~0#1|) (* |c_ULTIMATE.start_main_~yy~0#1| |c_ULTIMATE.start_main_~s~0#1| |c_ULTIMATE.start_main_~k~0#1|))) (< |c_ULTIMATE.start_main_~b~0#1| (+ |c_ULTIMATE.start_main_~c~0#1| 1))) is different from true [2024-10-24 00:11:45,698 WARN L286 SmtUtils]: Spent 5.19s on a formula simplification that was a NOOP. DAG size: 10 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify)