./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/egcd3-ll_valuebound20.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version fca748b1 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/egcd3-ll_valuebound20.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 39b854852f8258ff198098e27d83a5b0e296df48090ebea0d59d234417af0752 --- Real Ultimate output --- This is Ultimate 0.2.5-wip.dd.update-z3-fca748b-m [2024-11-19 21:17:59,353 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-19 21:17:59,417 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-19 21:17:59,423 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-19 21:17:59,425 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-19 21:17:59,450 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-19 21:17:59,450 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-19 21:17:59,451 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-19 21:17:59,451 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-19 21:17:59,455 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-19 21:17:59,455 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-19 21:17:59,456 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-19 21:17:59,456 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-19 21:17:59,456 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-19 21:17:59,457 INFO L153 SettingsManager]: * Use SBE=true [2024-11-19 21:17:59,457 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-19 21:17:59,457 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-19 21:17:59,457 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-19 21:17:59,457 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-19 21:17:59,458 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-19 21:17:59,458 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-19 21:17:59,459 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-19 21:17:59,459 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-19 21:17:59,459 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-19 21:17:59,459 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-19 21:17:59,460 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-19 21:17:59,460 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-19 21:17:59,460 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-19 21:17:59,461 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-19 21:17:59,461 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-19 21:17:59,462 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-19 21:17:59,462 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-19 21:17:59,462 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-19 21:17:59,462 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-19 21:17:59,463 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-19 21:17:59,463 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-19 21:17:59,463 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-19 21:17:59,463 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-19 21:17:59,463 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-19 21:17:59,463 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-19 21:17:59,464 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-19 21:17:59,464 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-19 21:17:59,464 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 -> 39b854852f8258ff198098e27d83a5b0e296df48090ebea0d59d234417af0752 [2024-11-19 21:17:59,706 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-19 21:17:59,755 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-19 21:17:59,758 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-19 21:17:59,759 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-19 21:17:59,763 INFO L274 PluginConnector]: CDTParser initialized [2024-11-19 21:17:59,764 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound20.c [2024-11-19 21:18:01,129 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-19 21:18:01,330 INFO L384 CDTParser]: Found 1 translation units. [2024-11-19 21:18:01,331 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound20.c [2024-11-19 21:18:01,346 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a10aaa1fc/9b0197e407ce457f86c867f8087835a8/FLAGf3c9b24ea [2024-11-19 21:18:01,358 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a10aaa1fc/9b0197e407ce457f86c867f8087835a8 [2024-11-19 21:18:01,361 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-19 21:18:01,362 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-19 21:18:01,363 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-19 21:18:01,363 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-19 21:18:01,369 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-19 21:18:01,369 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 09:18:01" (1/1) ... [2024-11-19 21:18:01,370 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@75f7f291 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:18:01, skipping insertion in model container [2024-11-19 21:18:01,370 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 09:18:01" (1/1) ... [2024-11-19 21:18:01,390 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-19 21:18:01,566 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound20.c[490,503] [2024-11-19 21:18:01,585 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-19 21:18:01,593 INFO L200 MainTranslator]: Completed pre-run [2024-11-19 21:18:01,604 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound20.c[490,503] [2024-11-19 21:18:01,612 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-19 21:18:01,629 INFO L204 MainTranslator]: Completed translation [2024-11-19 21:18:01,630 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:18:01 WrapperNode [2024-11-19 21:18:01,630 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-19 21:18:01,631 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-19 21:18:01,631 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-19 21:18:01,631 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-19 21:18:01,637 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:18:01" (1/1) ... [2024-11-19 21:18:01,644 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:18:01" (1/1) ... [2024-11-19 21:18:01,665 INFO L138 Inliner]: procedures = 14, calls = 16, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 83 [2024-11-19 21:18:01,666 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-19 21:18:01,667 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-19 21:18:01,667 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-19 21:18:01,667 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-19 21:18:01,678 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:18:01" (1/1) ... [2024-11-19 21:18:01,678 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:18:01" (1/1) ... [2024-11-19 21:18:01,679 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:18:01" (1/1) ... [2024-11-19 21:18:01,692 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-11-19 21:18:01,693 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:18:01" (1/1) ... [2024-11-19 21:18:01,693 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:18:01" (1/1) ... [2024-11-19 21:18:01,696 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:18:01" (1/1) ... [2024-11-19 21:18:01,701 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:18:01" (1/1) ... [2024-11-19 21:18:01,702 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:18:01" (1/1) ... [2024-11-19 21:18:01,703 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:18:01" (1/1) ... [2024-11-19 21:18:01,704 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-19 21:18:01,705 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-19 21:18:01,705 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-19 21:18:01,706 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-19 21:18:01,706 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:18:01" (1/1) ... [2024-11-19 21:18:01,712 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-19 21:18:01,720 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:18:01,736 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-19 21:18:01,742 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-19 21:18:01,778 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-19 21:18:01,778 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-19 21:18:01,778 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-19 21:18:01,779 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-19 21:18:01,779 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-19 21:18:01,779 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-19 21:18:01,779 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-19 21:18:01,779 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-19 21:18:01,825 INFO L238 CfgBuilder]: Building ICFG [2024-11-19 21:18:01,827 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-19 21:18:01,951 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-11-19 21:18:01,952 INFO L287 CfgBuilder]: Performing block encoding [2024-11-19 21:18:01,970 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-19 21:18:01,971 INFO L316 CfgBuilder]: Removed 3 assume(true) statements. [2024-11-19 21:18:01,971 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 09:18:01 BoogieIcfgContainer [2024-11-19 21:18:01,971 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-19 21:18:01,973 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-19 21:18:01,974 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-19 21:18:01,978 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-19 21:18:01,979 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 19.11 09:18:01" (1/3) ... [2024-11-19 21:18:01,980 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1cf9b01a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.11 09:18:01, skipping insertion in model container [2024-11-19 21:18:01,980 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:18:01" (2/3) ... [2024-11-19 21:18:01,981 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1cf9b01a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.11 09:18:01, skipping insertion in model container [2024-11-19 21:18:01,981 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 09:18:01" (3/3) ... [2024-11-19 21:18:01,983 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd3-ll_valuebound20.c [2024-11-19 21:18:01,998 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-19 21:18:01,998 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-19 21:18:02,047 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-19 21:18:02,053 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;@1dab0857, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-19 21:18:02,054 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-19 21:18:02,057 INFO L276 IsEmpty]: Start isEmpty. Operand has 35 states, 22 states have (on average 1.5454545454545454) internal successors, (34), 23 states have internal predecessors, (34), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-19 21:18:02,063 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-11-19 21:18:02,063 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:18:02,064 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:18:02,065 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:18:02,069 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:18:02,069 INFO L85 PathProgramCache]: Analyzing trace with hash 872320404, now seen corresponding path program 1 times [2024-11-19 21:18:02,076 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:18:02,076 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [605086028] [2024-11-19 21:18:02,077 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:02,077 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:18:02,165 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:02,224 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-19 21:18:02,227 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:02,235 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-19 21:18:02,237 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:02,245 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-19 21:18:02,247 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:02,253 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-19 21:18:02,254 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:02,263 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-19 21:18:02,263 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:18:02,264 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [605086028] [2024-11-19 21:18:02,264 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [605086028] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 21:18:02,265 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-19 21:18:02,265 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-19 21:18:02,266 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2139871987] [2024-11-19 21:18:02,267 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 21:18:02,271 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-19 21:18:02,271 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:18:02,312 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-19 21:18:02,313 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-19 21:18:02,315 INFO L87 Difference]: Start difference. First operand has 35 states, 22 states have (on average 1.5454545454545454) internal successors, (34), 23 states have internal predecessors, (34), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-19 21:18:02,358 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:18:02,358 INFO L93 Difference]: Finished difference Result 67 states and 109 transitions. [2024-11-19 21:18:02,360 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-19 21:18:02,361 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) Word has length 29 [2024-11-19 21:18:02,362 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:18:02,367 INFO L225 Difference]: With dead ends: 67 [2024-11-19 21:18:02,368 INFO L226 Difference]: Without dead ends: 31 [2024-11-19 21:18:02,370 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-19 21:18:02,373 INFO L432 NwaCegarLoop]: 44 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 44 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-19 21:18:02,373 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 44 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-19 21:18:02,386 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2024-11-19 21:18:02,398 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 31. [2024-11-19 21:18:02,400 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31 states, 19 states have (on average 1.2105263157894737) internal successors, (23), 20 states have internal predecessors, (23), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-19 21:18:02,401 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 40 transitions. [2024-11-19 21:18:02,402 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 40 transitions. Word has length 29 [2024-11-19 21:18:02,403 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:18:02,403 INFO L471 AbstractCegarLoop]: Abstraction has 31 states and 40 transitions. [2024-11-19 21:18:02,403 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-19 21:18:02,403 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 40 transitions. [2024-11-19 21:18:02,404 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2024-11-19 21:18:02,404 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:18:02,404 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:18:02,405 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-19 21:18:02,405 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:18:02,405 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:18:02,406 INFO L85 PathProgramCache]: Analyzing trace with hash 1714405113, now seen corresponding path program 1 times [2024-11-19 21:18:02,406 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:18:02,406 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1833961715] [2024-11-19 21:18:02,406 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:02,406 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:18:02,440 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:02,627 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-19 21:18:02,629 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:02,636 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-19 21:18:02,637 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:02,643 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-19 21:18:02,649 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:02,652 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-19 21:18:02,656 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:02,704 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 9 proven. 0 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-19 21:18:02,704 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:18:02,704 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1833961715] [2024-11-19 21:18:02,705 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1833961715] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 21:18:02,705 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-19 21:18:02,705 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-19 21:18:02,705 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [391281778] [2024-11-19 21:18:02,705 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 21:18:02,707 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-19 21:18:02,708 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:18:02,709 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-19 21:18:02,710 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-19 21:18:02,711 INFO L87 Difference]: Start difference. First operand 31 states and 40 transitions. Second operand has 6 states, 6 states have (on average 2.5) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-19 21:18:02,813 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:18:02,813 INFO L93 Difference]: Finished difference Result 50 states and 65 transitions. [2024-11-19 21:18:02,814 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-19 21:18:02,814 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) Word has length 30 [2024-11-19 21:18:02,815 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:18:02,815 INFO L225 Difference]: With dead ends: 50 [2024-11-19 21:18:02,816 INFO L226 Difference]: Without dead ends: 43 [2024-11-19 21:18:02,816 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-19 21:18:02,817 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 28 mSDsluCounter, 72 mSDsCounter, 0 mSdLazyCounter, 54 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 36 SdHoareTripleChecker+Valid, 102 SdHoareTripleChecker+Invalid, 58 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 54 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-19 21:18:02,818 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [36 Valid, 102 Invalid, 58 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 54 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-19 21:18:02,818 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2024-11-19 21:18:02,827 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 33. [2024-11-19 21:18:02,827 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 21 states have (on average 1.1904761904761905) internal successors, (25), 22 states have internal predecessors, (25), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-19 21:18:02,828 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 42 transitions. [2024-11-19 21:18:02,829 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 42 transitions. Word has length 30 [2024-11-19 21:18:02,829 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:18:02,829 INFO L471 AbstractCegarLoop]: Abstraction has 33 states and 42 transitions. [2024-11-19 21:18:02,829 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-19 21:18:02,830 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 42 transitions. [2024-11-19 21:18:02,830 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2024-11-19 21:18:02,831 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:18:02,831 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:18:02,831 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-19 21:18:02,831 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:18:02,832 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:18:02,832 INFO L85 PathProgramCache]: Analyzing trace with hash -1825736765, now seen corresponding path program 1 times [2024-11-19 21:18:02,832 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:18:02,833 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1242149645] [2024-11-19 21:18:02,833 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:02,833 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:18:02,863 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:18:02,868 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1339456446] [2024-11-19 21:18:02,869 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:02,869 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:18:02,870 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:18:02,873 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:18:02,875 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-19 21:18:02,936 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:02,938 INFO L255 TraceCheckSpWp]: Trace formula consists of 95 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-19 21:18:02,945 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:18:03,080 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-19 21:18:03,080 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-19 21:18:03,080 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:18:03,080 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1242149645] [2024-11-19 21:18:03,081 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-19 21:18:03,081 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1339456446] [2024-11-19 21:18:03,082 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1339456446] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 21:18:03,082 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-19 21:18:03,082 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-19 21:18:03,082 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1697540791] [2024-11-19 21:18:03,082 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 21:18:03,083 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-19 21:18:03,083 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:18:03,084 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-19 21:18:03,084 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-19 21:18:03,084 INFO L87 Difference]: Start difference. First operand 33 states and 42 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, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-19 21:18:03,136 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:18:03,136 INFO L93 Difference]: Finished difference Result 49 states and 63 transitions. [2024-11-19 21:18:03,139 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-19 21:18:03,139 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, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 33 [2024-11-19 21:18:03,140 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:18:03,141 INFO L225 Difference]: With dead ends: 49 [2024-11-19 21:18:03,141 INFO L226 Difference]: Without dead ends: 47 [2024-11-19 21:18:03,141 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 33 GetRequests, 29 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-19 21:18:03,145 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 7 mSDsluCounter, 99 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 134 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-19 21:18:03,146 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 134 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-19 21:18:03,146 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2024-11-19 21:18:03,165 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 46. [2024-11-19 21:18:03,167 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 29 states have (on average 1.206896551724138) internal successors, (35), 30 states have internal predecessors, (35), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-19 21:18:03,168 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 60 transitions. [2024-11-19 21:18:03,170 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 60 transitions. Word has length 33 [2024-11-19 21:18:03,171 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:18:03,171 INFO L471 AbstractCegarLoop]: Abstraction has 46 states and 60 transitions. [2024-11-19 21:18:03,172 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, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-19 21:18:03,172 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 60 transitions. [2024-11-19 21:18:03,173 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2024-11-19 21:18:03,174 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:18:03,174 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:18:03,183 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-19 21:18:03,378 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:18:03,379 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:18:03,379 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:18:03,379 INFO L85 PathProgramCache]: Analyzing trace with hash -1547103247, now seen corresponding path program 1 times [2024-11-19 21:18:03,379 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:18:03,380 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2136086336] [2024-11-19 21:18:03,380 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:03,380 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:18:03,395 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:03,531 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-19 21:18:03,532 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:03,536 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-19 21:18:03,538 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:03,542 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-19 21:18:03,543 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:03,577 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-19 21:18:03,581 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:03,586 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 6 proven. 5 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-19 21:18:03,588 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:18:03,588 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2136086336] [2024-11-19 21:18:03,589 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2136086336] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 21:18:03,589 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1497872046] [2024-11-19 21:18:03,591 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:03,591 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:18:03,592 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:18:03,593 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:18:03,597 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-19 21:18:03,642 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:03,643 INFO L255 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-19 21:18:03,644 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:18:03,712 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 6 proven. 5 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-19 21:18:03,714 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 21:18:03,824 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 6 proven. 5 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-19 21:18:03,827 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1497872046] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 21:18:03,827 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 21:18:03,828 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 12 [2024-11-19 21:18:03,828 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [127177936] [2024-11-19 21:18:03,828 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 21:18:03,828 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-19 21:18:03,828 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:18:03,829 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-19 21:18:03,829 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=103, Unknown=0, NotChecked=0, Total=132 [2024-11-19 21:18:03,829 INFO L87 Difference]: Start difference. First operand 46 states and 60 transitions. Second operand has 12 states, 12 states have (on average 2.5) internal successors, (30), 11 states have internal predecessors, (30), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-19 21:18:04,103 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:18:04,104 INFO L93 Difference]: Finished difference Result 99 states and 139 transitions. [2024-11-19 21:18:04,106 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-19 21:18:04,106 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.5) internal successors, (30), 11 states have internal predecessors, (30), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 35 [2024-11-19 21:18:04,107 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:18:04,108 INFO L225 Difference]: With dead ends: 99 [2024-11-19 21:18:04,108 INFO L226 Difference]: Without dead ends: 92 [2024-11-19 21:18:04,109 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 86 GetRequests, 69 SyntacticMatches, 4 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 44 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=54, Invalid=156, Unknown=0, NotChecked=0, Total=210 [2024-11-19 21:18:04,110 INFO L432 NwaCegarLoop]: 40 mSDtfsCounter, 67 mSDsluCounter, 194 mSDsCounter, 0 mSdLazyCounter, 132 mSolverCounterSat, 31 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 75 SdHoareTripleChecker+Valid, 234 SdHoareTripleChecker+Invalid, 163 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 31 IncrementalHoareTripleChecker+Valid, 132 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-19 21:18:04,110 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [75 Valid, 234 Invalid, 163 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [31 Valid, 132 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-19 21:18:04,113 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2024-11-19 21:18:04,135 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 67. [2024-11-19 21:18:04,136 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 67 states, 46 states have (on average 1.2608695652173914) internal successors, (58), 47 states have internal predecessors, (58), 17 states have call successors, (17), 3 states have call predecessors, (17), 3 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2024-11-19 21:18:04,138 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 91 transitions. [2024-11-19 21:18:04,141 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 91 transitions. Word has length 35 [2024-11-19 21:18:04,142 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:18:04,142 INFO L471 AbstractCegarLoop]: Abstraction has 67 states and 91 transitions. [2024-11-19 21:18:04,142 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 2.5) internal successors, (30), 11 states have internal predecessors, (30), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-19 21:18:04,142 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 91 transitions. [2024-11-19 21:18:04,143 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2024-11-19 21:18:04,143 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:18:04,143 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:18:04,153 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-19 21:18:04,343 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable3 [2024-11-19 21:18:04,344 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:18:04,344 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:18:04,344 INFO L85 PathProgramCache]: Analyzing trace with hash -720434099, now seen corresponding path program 1 times [2024-11-19 21:18:04,345 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:18:04,345 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1688589348] [2024-11-19 21:18:04,345 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:04,345 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:18:04,363 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:18:04,364 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [984920702] [2024-11-19 21:18:04,364 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:04,364 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:18:04,365 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:18:04,369 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:18:04,371 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-19 21:18:04,411 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:04,419 INFO L255 TraceCheckSpWp]: Trace formula consists of 104 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-19 21:18:04,421 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:18:04,509 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-19 21:18:04,512 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-19 21:18:04,512 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:18:04,512 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1688589348] [2024-11-19 21:18:04,513 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-19 21:18:04,513 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [984920702] [2024-11-19 21:18:04,513 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [984920702] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 21:18:04,513 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-19 21:18:04,513 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-19 21:18:04,513 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1044149138] [2024-11-19 21:18:04,513 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 21:18:04,514 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-19 21:18:04,514 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:18:04,514 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-19 21:18:04,514 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-19 21:18:04,515 INFO L87 Difference]: Start difference. First operand 67 states and 91 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-19 21:18:04,576 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:18:04,576 INFO L93 Difference]: Finished difference Result 75 states and 98 transitions. [2024-11-19 21:18:04,577 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-19 21:18:04,577 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 38 [2024-11-19 21:18:04,579 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:18:04,580 INFO L225 Difference]: With dead ends: 75 [2024-11-19 21:18:04,580 INFO L226 Difference]: Without dead ends: 73 [2024-11-19 21:18:04,580 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 38 GetRequests, 34 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-19 21:18:04,581 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 7 mSDsluCounter, 95 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 131 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-19 21:18:04,582 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 131 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-19 21:18:04,583 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2024-11-19 21:18:04,601 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 71. [2024-11-19 21:18:04,603 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 49 states have (on average 1.2448979591836735) internal successors, (61), 50 states have internal predecessors, (61), 17 states have call successors, (17), 4 states have call predecessors, (17), 4 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2024-11-19 21:18:04,605 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 94 transitions. [2024-11-19 21:18:04,607 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 94 transitions. Word has length 38 [2024-11-19 21:18:04,607 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:18:04,608 INFO L471 AbstractCegarLoop]: Abstraction has 71 states and 94 transitions. [2024-11-19 21:18:04,608 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-19 21:18:04,608 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 94 transitions. [2024-11-19 21:18:04,609 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2024-11-19 21:18:04,609 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:18:04,611 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:18:04,619 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-19 21:18:04,811 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:18:04,812 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:18:04,812 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:18:04,812 INFO L85 PathProgramCache]: Analyzing trace with hash -376152117, now seen corresponding path program 1 times [2024-11-19 21:18:04,812 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:18:04,812 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1050085597] [2024-11-19 21:18:04,812 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:04,813 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:18:04,826 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:18:04,827 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [404468861] [2024-11-19 21:18:04,827 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:04,827 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:18:04,827 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:18:04,829 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:18:04,831 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-19 21:18:04,872 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:04,873 INFO L255 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-11-19 21:18:04,875 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:18:05,003 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-19 21:18:05,004 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 21:18:05,107 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-19 21:18:05,111 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:18:05,111 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1050085597] [2024-11-19 21:18:05,111 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-19 21:18:05,111 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [404468861] [2024-11-19 21:18:05,111 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [404468861] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 21:18:05,112 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-19 21:18:05,112 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 6] total 9 [2024-11-19 21:18:05,112 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1219695221] [2024-11-19 21:18:05,112 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-19 21:18:05,112 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-19 21:18:05,112 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:18:05,113 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-19 21:18:05,113 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2024-11-19 21:18:05,113 INFO L87 Difference]: Start difference. First operand 71 states and 94 transitions. Second operand has 9 states, 9 states have (on average 3.4444444444444446) internal successors, (31), 8 states have internal predecessors, (31), 3 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-19 21:18:05,269 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:18:05,270 INFO L93 Difference]: Finished difference Result 107 states and 143 transitions. [2024-11-19 21:18:05,271 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-19 21:18:05,271 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 3.4444444444444446) internal successors, (31), 8 states have internal predecessors, (31), 3 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 38 [2024-11-19 21:18:05,271 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:18:05,272 INFO L225 Difference]: With dead ends: 107 [2024-11-19 21:18:05,272 INFO L226 Difference]: Without dead ends: 105 [2024-11-19 21:18:05,273 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 65 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=29, Invalid=81, Unknown=0, NotChecked=0, Total=110 [2024-11-19 21:18:05,273 INFO L432 NwaCegarLoop]: 47 mSDtfsCounter, 30 mSDsluCounter, 188 mSDsCounter, 0 mSdLazyCounter, 82 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 235 SdHoareTripleChecker+Invalid, 100 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 82 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-19 21:18:05,273 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 235 Invalid, 100 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 82 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-19 21:18:05,278 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 105 states. [2024-11-19 21:18:05,302 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 105 to 101. [2024-11-19 21:18:05,304 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 101 states, 70 states have (on average 1.2571428571428571) internal successors, (88), 71 states have internal predecessors, (88), 25 states have call successors, (25), 5 states have call predecessors, (25), 5 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) [2024-11-19 21:18:05,306 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 101 states to 101 states and 137 transitions. [2024-11-19 21:18:05,308 INFO L78 Accepts]: Start accepts. Automaton has 101 states and 137 transitions. Word has length 38 [2024-11-19 21:18:05,308 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:18:05,308 INFO L471 AbstractCegarLoop]: Abstraction has 101 states and 137 transitions. [2024-11-19 21:18:05,309 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 3.4444444444444446) internal successors, (31), 8 states have internal predecessors, (31), 3 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-19 21:18:05,309 INFO L276 IsEmpty]: Start isEmpty. Operand 101 states and 137 transitions. [2024-11-19 21:18:05,310 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2024-11-19 21:18:05,310 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:18:05,310 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:18:05,320 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-19 21:18:05,514 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:18:05,515 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:18:05,515 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:18:05,515 INFO L85 PathProgramCache]: Analyzing trace with hash 279172547, now seen corresponding path program 1 times [2024-11-19 21:18:05,515 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:18:05,515 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [211376415] [2024-11-19 21:18:05,515 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:05,515 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:18:05,527 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:18:05,528 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1796906694] [2024-11-19 21:18:05,528 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:05,528 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:18:05,528 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:18:05,531 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:18:05,534 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-19 21:18:05,572 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:05,573 INFO L255 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-19 21:18:05,575 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:18:05,629 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-19 21:18:05,629 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-19 21:18:05,629 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:18:05,630 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [211376415] [2024-11-19 21:18:05,630 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-19 21:18:05,630 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1796906694] [2024-11-19 21:18:05,630 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1796906694] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 21:18:05,630 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-19 21:18:05,630 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-19 21:18:05,631 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2074129085] [2024-11-19 21:18:05,631 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 21:18:05,631 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-19 21:18:05,632 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:18:05,632 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-19 21:18:05,632 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-19 21:18:05,633 INFO L87 Difference]: Start difference. First operand 101 states and 137 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2024-11-19 21:18:05,710 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:18:05,710 INFO L93 Difference]: Finished difference Result 147 states and 209 transitions. [2024-11-19 21:18:05,711 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-19 21:18:05,711 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 43 [2024-11-19 21:18:05,711 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:18:05,713 INFO L225 Difference]: With dead ends: 147 [2024-11-19 21:18:05,713 INFO L226 Difference]: Without dead ends: 145 [2024-11-19 21:18:05,713 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 39 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-19 21:18:05,714 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 6 mSDsluCounter, 90 mSDsCounter, 0 mSdLazyCounter, 43 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 43 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-19 21:18:05,715 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 124 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 43 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-19 21:18:05,715 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 145 states. [2024-11-19 21:18:05,756 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 145 to 139. [2024-11-19 21:18:05,757 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 139 states, 87 states have (on average 1.2873563218390804) internal successors, (112), 88 states have internal predecessors, (112), 45 states have call successors, (45), 6 states have call predecessors, (45), 6 states have return successors, (44), 44 states have call predecessors, (44), 44 states have call successors, (44) [2024-11-19 21:18:05,759 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 139 states to 139 states and 201 transitions. [2024-11-19 21:18:05,762 INFO L78 Accepts]: Start accepts. Automaton has 139 states and 201 transitions. Word has length 43 [2024-11-19 21:18:05,762 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:18:05,763 INFO L471 AbstractCegarLoop]: Abstraction has 139 states and 201 transitions. [2024-11-19 21:18:05,763 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2024-11-19 21:18:05,763 INFO L276 IsEmpty]: Start isEmpty. Operand 139 states and 201 transitions. [2024-11-19 21:18:05,764 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2024-11-19 21:18:05,764 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:18:05,764 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:18:05,772 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-19 21:18:05,964 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:18:05,965 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:18:05,966 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:18:05,966 INFO L85 PathProgramCache]: Analyzing trace with hash -2141198011, now seen corresponding path program 1 times [2024-11-19 21:18:05,966 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:18:05,966 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [147230411] [2024-11-19 21:18:05,966 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:05,967 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:18:05,988 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:18:05,989 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [374465548] [2024-11-19 21:18:05,990 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:05,990 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:18:05,990 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:18:05,993 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:18:05,995 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-19 21:18:06,037 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:06,041 INFO L255 TraceCheckSpWp]: Trace formula consists of 124 conjuncts, 21 conjuncts are in the unsatisfiable core [2024-11-19 21:18:06,044 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:18:06,183 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 2 proven. 4 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-19 21:18:06,183 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 21:18:06,248 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:18:06,248 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [147230411] [2024-11-19 21:18:06,248 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-19 21:18:06,248 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [374465548] [2024-11-19 21:18:06,249 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [374465548] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 21:18:06,249 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-19 21:18:06,249 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2024-11-19 21:18:06,249 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1174165292] [2024-11-19 21:18:06,249 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-19 21:18:06,249 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-19 21:18:06,250 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:18:06,250 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-19 21:18:06,250 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2024-11-19 21:18:06,250 INFO L87 Difference]: Start difference. First operand 139 states and 201 transitions. Second operand has 7 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 6 states have internal predecessors, (23), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-19 21:18:06,399 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:18:06,399 INFO L93 Difference]: Finished difference Result 152 states and 212 transitions. [2024-11-19 21:18:06,400 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-19 21:18:06,400 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 6 states have internal predecessors, (23), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 43 [2024-11-19 21:18:06,400 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:18:06,402 INFO L225 Difference]: With dead ends: 152 [2024-11-19 21:18:06,402 INFO L226 Difference]: Without dead ends: 150 [2024-11-19 21:18:06,403 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 39 SyntacticMatches, 2 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2024-11-19 21:18:06,403 INFO L432 NwaCegarLoop]: 42 mSDtfsCounter, 26 mSDsluCounter, 167 mSDsCounter, 0 mSdLazyCounter, 109 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 209 SdHoareTripleChecker+Invalid, 120 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 109 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-19 21:18:06,403 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [33 Valid, 209 Invalid, 120 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 109 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-19 21:18:06,404 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 150 states. [2024-11-19 21:18:06,437 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 150 to 147. [2024-11-19 21:18:06,437 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 147 states, 93 states have (on average 1.2688172043010753) internal successors, (118), 94 states have internal predecessors, (118), 45 states have call successors, (45), 8 states have call predecessors, (45), 8 states have return successors, (44), 44 states have call predecessors, (44), 44 states have call successors, (44) [2024-11-19 21:18:06,438 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 147 states to 147 states and 207 transitions. [2024-11-19 21:18:06,439 INFO L78 Accepts]: Start accepts. Automaton has 147 states and 207 transitions. Word has length 43 [2024-11-19 21:18:06,439 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:18:06,439 INFO L471 AbstractCegarLoop]: Abstraction has 147 states and 207 transitions. [2024-11-19 21:18:06,439 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 6 states have internal predecessors, (23), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-19 21:18:06,439 INFO L276 IsEmpty]: Start isEmpty. Operand 147 states and 207 transitions. [2024-11-19 21:18:06,440 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2024-11-19 21:18:06,440 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:18:06,440 INFO L215 NwaCegarLoop]: trace histogram [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-11-19 21:18:06,449 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-11-19 21:18:06,644 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:18:06,645 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:18:06,645 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:18:06,645 INFO L85 PathProgramCache]: Analyzing trace with hash -1796916029, now seen corresponding path program 2 times [2024-11-19 21:18:06,645 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:18:06,645 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1424549462] [2024-11-19 21:18:06,645 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:06,645 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:18:06,654 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:06,715 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-19 21:18:06,716 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:06,718 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-19 21:18:06,719 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:06,720 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-19 21:18:06,721 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:06,722 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-19 21:18:06,723 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:06,724 INFO L134 CoverageAnalysis]: Checked inductivity of 37 backedges. 13 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-19 21:18:06,724 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:18:06,724 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1424549462] [2024-11-19 21:18:06,724 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1424549462] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 21:18:06,724 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-19 21:18:06,724 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-19 21:18:06,724 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1167915538] [2024-11-19 21:18:06,725 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 21:18:06,725 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-19 21:18:06,725 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:18:06,725 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-19 21:18:06,725 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-19 21:18:06,726 INFO L87 Difference]: Start difference. First operand 147 states and 207 transitions. Second operand has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-19 21:18:06,826 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:18:06,826 INFO L93 Difference]: Finished difference Result 186 states and 259 transitions. [2024-11-19 21:18:06,826 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-19 21:18:06,826 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), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 43 [2024-11-19 21:18:06,826 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:18:06,827 INFO L225 Difference]: With dead ends: 186 [2024-11-19 21:18:06,828 INFO L226 Difference]: Without dead ends: 130 [2024-11-19 21:18:06,828 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2024-11-19 21:18:06,829 INFO L432 NwaCegarLoop]: 49 mSDtfsCounter, 18 mSDsluCounter, 111 mSDsCounter, 0 mSdLazyCounter, 54 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 160 SdHoareTripleChecker+Invalid, 62 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 54 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-19 21:18:06,829 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 160 Invalid, 62 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 54 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-19 21:18:06,830 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2024-11-19 21:18:06,847 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 122. [2024-11-19 21:18:06,847 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 122 states, 76 states have (on average 1.2105263157894737) internal successors, (92), 77 states have internal predecessors, (92), 37 states have call successors, (37), 8 states have call predecessors, (37), 8 states have return successors, (36), 36 states have call predecessors, (36), 36 states have call successors, (36) [2024-11-19 21:18:06,848 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 122 states to 122 states and 165 transitions. [2024-11-19 21:18:06,848 INFO L78 Accepts]: Start accepts. Automaton has 122 states and 165 transitions. Word has length 43 [2024-11-19 21:18:06,849 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:18:06,849 INFO L471 AbstractCegarLoop]: Abstraction has 122 states and 165 transitions. [2024-11-19 21:18:06,849 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), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-19 21:18:06,849 INFO L276 IsEmpty]: Start isEmpty. Operand 122 states and 165 transitions. [2024-11-19 21:18:06,850 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2024-11-19 21:18:06,850 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:18:06,850 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:18:06,850 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8 [2024-11-19 21:18:06,850 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:18:06,850 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:18:06,850 INFO L85 PathProgramCache]: Analyzing trace with hash -1189241395, now seen corresponding path program 1 times [2024-11-19 21:18:06,851 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:18:06,851 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1618637465] [2024-11-19 21:18:06,851 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:06,851 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:18:06,865 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:18:06,868 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2116953251] [2024-11-19 21:18:06,868 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:06,869 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:18:06,869 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:18:06,870 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:18:06,873 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-19 21:18:06,913 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:06,914 INFO L255 TraceCheckSpWp]: Trace formula consists of 122 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-19 21:18:06,915 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:18:06,959 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-11-19 21:18:06,959 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-19 21:18:06,959 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:18:06,959 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1618637465] [2024-11-19 21:18:06,959 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-19 21:18:06,959 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2116953251] [2024-11-19 21:18:06,960 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2116953251] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 21:18:06,960 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-19 21:18:06,960 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-19 21:18:06,960 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1643950426] [2024-11-19 21:18:06,960 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 21:18:06,960 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-19 21:18:06,960 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:18:06,961 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-19 21:18:06,961 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-19 21:18:06,961 INFO L87 Difference]: Start difference. First operand 122 states and 165 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-19 21:18:07,035 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:18:07,035 INFO L93 Difference]: Finished difference Result 180 states and 262 transitions. [2024-11-19 21:18:07,035 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-19 21:18:07,036 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (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 48 [2024-11-19 21:18:07,037 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:18:07,039 INFO L225 Difference]: With dead ends: 180 [2024-11-19 21:18:07,039 INFO L226 Difference]: Without dead ends: 178 [2024-11-19 21:18:07,041 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 48 GetRequests, 44 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-19 21:18:07,041 INFO L432 NwaCegarLoop]: 37 mSDtfsCounter, 4 mSDsluCounter, 95 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 132 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-19 21:18:07,042 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 132 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-19 21:18:07,042 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 178 states. [2024-11-19 21:18:07,078 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 178 to 166. [2024-11-19 21:18:07,079 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 166 states, 87 states have (on average 1.1839080459770115) internal successors, (103), 96 states have internal predecessors, (103), 69 states have call successors, (69), 9 states have call predecessors, (69), 9 states have return successors, (68), 60 states have call predecessors, (68), 68 states have call successors, (68) [2024-11-19 21:18:07,080 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 166 states to 166 states and 240 transitions. [2024-11-19 21:18:07,081 INFO L78 Accepts]: Start accepts. Automaton has 166 states and 240 transitions. Word has length 48 [2024-11-19 21:18:07,081 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:18:07,081 INFO L471 AbstractCegarLoop]: Abstraction has 166 states and 240 transitions. [2024-11-19 21:18:07,081 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-19 21:18:07,081 INFO L276 IsEmpty]: Start isEmpty. Operand 166 states and 240 transitions. [2024-11-19 21:18:07,083 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2024-11-19 21:18:07,083 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:18:07,083 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:18:07,091 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-19 21:18:07,283 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:18:07,284 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:18:07,284 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:18:07,284 INFO L85 PathProgramCache]: Analyzing trace with hash -828341661, now seen corresponding path program 1 times [2024-11-19 21:18:07,285 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:18:07,285 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1084582916] [2024-11-19 21:18:07,285 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:07,285 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:18:07,306 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:18:07,307 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [897461709] [2024-11-19 21:18:07,307 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:07,307 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:18:07,307 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:18:07,310 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:18:07,311 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-19 21:18:07,363 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:07,364 INFO L255 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 51 conjuncts are in the unsatisfiable core [2024-11-19 21:18:07,367 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:18:08,093 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 14 proven. 7 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-19 21:18:08,093 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 21:18:08,612 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 8 proven. 4 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-11-19 21:18:08,612 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:18:08,613 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1084582916] [2024-11-19 21:18:08,613 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-19 21:18:08,613 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [897461709] [2024-11-19 21:18:08,613 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [897461709] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 21:18:08,613 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-19 21:18:08,613 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 23 [2024-11-19 21:18:08,614 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [221622646] [2024-11-19 21:18:08,614 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-19 21:18:08,614 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-11-19 21:18:08,614 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:18:08,615 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-19 21:18:08,615 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=77, Invalid=429, Unknown=0, NotChecked=0, Total=506 [2024-11-19 21:18:08,615 INFO L87 Difference]: Start difference. First operand 166 states and 240 transitions. Second operand has 23 states, 21 states have (on average 2.0476190476190474) internal successors, (43), 20 states have internal predecessors, (43), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2024-11-19 21:18:10,807 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:18:10,807 INFO L93 Difference]: Finished difference Result 445 states and 665 transitions. [2024-11-19 21:18:10,808 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2024-11-19 21:18:10,808 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 21 states have (on average 2.0476190476190474) internal successors, (43), 20 states have internal predecessors, (43), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) Word has length 60 [2024-11-19 21:18:10,809 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:18:10,814 INFO L225 Difference]: With dead ends: 445 [2024-11-19 21:18:10,815 INFO L226 Difference]: Without dead ends: 342 [2024-11-19 21:18:10,819 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 141 GetRequests, 97 SyntacticMatches, 0 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 429 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=398, Invalid=1672, Unknown=0, NotChecked=0, Total=2070 [2024-11-19 21:18:10,819 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 167 mSDsluCounter, 361 mSDsCounter, 0 mSdLazyCounter, 593 mSolverCounterSat, 148 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 175 SdHoareTripleChecker+Valid, 391 SdHoareTripleChecker+Invalid, 741 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 148 IncrementalHoareTripleChecker+Valid, 593 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2024-11-19 21:18:10,820 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [175 Valid, 391 Invalid, 741 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [148 Valid, 593 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2024-11-19 21:18:10,820 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 342 states. [2024-11-19 21:18:10,929 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 342 to 256. [2024-11-19 21:18:10,930 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 256 states, 150 states have (on average 1.2066666666666668) internal successors, (181), 157 states have internal predecessors, (181), 93 states have call successors, (93), 12 states have call predecessors, (93), 12 states have return successors, (92), 86 states have call predecessors, (92), 92 states have call successors, (92) [2024-11-19 21:18:10,933 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 256 states to 256 states and 366 transitions. [2024-11-19 21:18:10,934 INFO L78 Accepts]: Start accepts. Automaton has 256 states and 366 transitions. Word has length 60 [2024-11-19 21:18:10,934 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:18:10,935 INFO L471 AbstractCegarLoop]: Abstraction has 256 states and 366 transitions. [2024-11-19 21:18:10,935 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 21 states have (on average 2.0476190476190474) internal successors, (43), 20 states have internal predecessors, (43), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2024-11-19 21:18:10,935 INFO L276 IsEmpty]: Start isEmpty. Operand 256 states and 366 transitions. [2024-11-19 21:18:10,936 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2024-11-19 21:18:10,937 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:18:10,937 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 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-11-19 21:18:10,945 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2024-11-19 21:18:11,138 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2024-11-19 21:18:11,138 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:18:11,139 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:18:11,139 INFO L85 PathProgramCache]: Analyzing trace with hash 1607561902, now seen corresponding path program 1 times [2024-11-19 21:18:11,139 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:18:11,139 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [722731981] [2024-11-19 21:18:11,139 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:11,139 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:18:11,163 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:18:11,167 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [264713320] [2024-11-19 21:18:11,167 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:11,167 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:18:11,167 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:18:11,173 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:18:11,177 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-19 21:18:11,228 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:11,229 INFO L255 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-11-19 21:18:11,231 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:18:11,305 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 14 proven. 5 refuted. 0 times theorem prover too weak. 108 trivial. 0 not checked. [2024-11-19 21:18:11,305 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 21:18:11,381 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 14 proven. 0 refuted. 0 times theorem prover too weak. 113 trivial. 0 not checked. [2024-11-19 21:18:11,381 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:18:11,381 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [722731981] [2024-11-19 21:18:11,381 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-19 21:18:11,381 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [264713320] [2024-11-19 21:18:11,382 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [264713320] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-19 21:18:11,382 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-19 21:18:11,382 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2024-11-19 21:18:11,382 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1587474315] [2024-11-19 21:18:11,382 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 21:18:11,383 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-19 21:18:11,383 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:18:11,383 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-19 21:18:11,383 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-19 21:18:11,384 INFO L87 Difference]: Start difference. First operand 256 states and 366 transitions. Second operand has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-11-19 21:18:11,525 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:18:11,526 INFO L93 Difference]: Finished difference Result 262 states and 371 transitions. [2024-11-19 21:18:11,526 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-19 21:18:11,526 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 70 [2024-11-19 21:18:11,527 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:18:11,529 INFO L225 Difference]: With dead ends: 262 [2024-11-19 21:18:11,529 INFO L226 Difference]: Without dead ends: 260 [2024-11-19 21:18:11,529 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 139 GetRequests, 131 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-19 21:18:11,530 INFO L432 NwaCegarLoop]: 37 mSDtfsCounter, 4 mSDsluCounter, 90 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 127 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-19 21:18:11,530 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 127 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-19 21:18:11,531 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 260 states. [2024-11-19 21:18:11,622 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 260 to 260. [2024-11-19 21:18:11,623 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 260 states, 153 states have (on average 1.2026143790849673) internal successors, (184), 160 states have internal predecessors, (184), 93 states have call successors, (93), 13 states have call predecessors, (93), 13 states have return successors, (92), 86 states have call predecessors, (92), 92 states have call successors, (92) [2024-11-19 21:18:11,625 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 260 states to 260 states and 369 transitions. [2024-11-19 21:18:11,626 INFO L78 Accepts]: Start accepts. Automaton has 260 states and 369 transitions. Word has length 70 [2024-11-19 21:18:11,626 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:18:11,626 INFO L471 AbstractCegarLoop]: Abstraction has 260 states and 369 transitions. [2024-11-19 21:18:11,626 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-11-19 21:18:11,626 INFO L276 IsEmpty]: Start isEmpty. Operand 260 states and 369 transitions. [2024-11-19 21:18:11,627 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2024-11-19 21:18:11,627 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:18:11,628 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:18:11,636 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2024-11-19 21:18:11,831 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:18:11,832 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:18:11,832 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:18:11,832 INFO L85 PathProgramCache]: Analyzing trace with hash -1439093215, now seen corresponding path program 1 times [2024-11-19 21:18:11,832 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:18:11,833 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1977304612] [2024-11-19 21:18:11,833 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:11,833 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:18:11,854 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:18:11,855 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1148339116] [2024-11-19 21:18:11,855 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:11,855 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:18:11,856 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:18:11,858 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:18:11,859 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-19 21:18:11,907 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:11,909 INFO L255 TraceCheckSpWp]: Trace formula consists of 183 conjuncts, 50 conjuncts are in the unsatisfiable core [2024-11-19 21:18:11,911 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:18:12,472 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 16 proven. 31 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2024-11-19 21:18:12,472 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 21:18:12,658 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 25 proven. 9 refuted. 0 times theorem prover too weak. 43 trivial. 0 not checked. [2024-11-19 21:18:12,658 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:18:12,658 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1977304612] [2024-11-19 21:18:12,658 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-19 21:18:12,658 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1148339116] [2024-11-19 21:18:12,659 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1148339116] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 21:18:12,659 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-19 21:18:12,659 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 8] total 22 [2024-11-19 21:18:12,659 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1672729763] [2024-11-19 21:18:12,659 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-19 21:18:12,659 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-11-19 21:18:12,659 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:18:12,660 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-19 21:18:12,660 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=395, Unknown=0, NotChecked=0, Total=462 [2024-11-19 21:18:12,660 INFO L87 Difference]: Start difference. First operand 260 states and 369 transitions. Second operand has 22 states, 22 states have (on average 2.772727272727273) internal successors, (61), 19 states have internal predecessors, (61), 6 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2024-11-19 21:18:14,003 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:18:14,003 INFO L93 Difference]: Finished difference Result 322 states and 459 transitions. [2024-11-19 21:18:14,004 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-11-19 21:18:14,004 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 2.772727272727273) internal successors, (61), 19 states have internal predecessors, (61), 6 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) Word has length 68 [2024-11-19 21:18:14,004 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:18:14,007 INFO L225 Difference]: With dead ends: 322 [2024-11-19 21:18:14,007 INFO L226 Difference]: Without dead ends: 320 [2024-11-19 21:18:14,007 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 155 GetRequests, 123 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 193 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=190, Invalid=932, Unknown=0, NotChecked=0, Total=1122 [2024-11-19 21:18:14,008 INFO L432 NwaCegarLoop]: 52 mSDtfsCounter, 114 mSDsluCounter, 524 mSDsCounter, 0 mSdLazyCounter, 628 mSolverCounterSat, 91 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 116 SdHoareTripleChecker+Valid, 576 SdHoareTripleChecker+Invalid, 719 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 91 IncrementalHoareTripleChecker+Valid, 628 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2024-11-19 21:18:14,008 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [116 Valid, 576 Invalid, 719 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [91 Valid, 628 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2024-11-19 21:18:14,008 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 320 states. [2024-11-19 21:18:14,106 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 320 to 268. [2024-11-19 21:18:14,106 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 268 states, 159 states have (on average 1.1949685534591195) internal successors, (190), 166 states have internal predecessors, (190), 93 states have call successors, (93), 15 states have call predecessors, (93), 15 states have return successors, (92), 86 states have call predecessors, (92), 92 states have call successors, (92) [2024-11-19 21:18:14,108 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 268 states to 268 states and 375 transitions. [2024-11-19 21:18:14,108 INFO L78 Accepts]: Start accepts. Automaton has 268 states and 375 transitions. Word has length 68 [2024-11-19 21:18:14,108 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:18:14,108 INFO L471 AbstractCegarLoop]: Abstraction has 268 states and 375 transitions. [2024-11-19 21:18:14,109 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 2.772727272727273) internal successors, (61), 19 states have internal predecessors, (61), 6 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2024-11-19 21:18:14,109 INFO L276 IsEmpty]: Start isEmpty. Operand 268 states and 375 transitions. [2024-11-19 21:18:14,109 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2024-11-19 21:18:14,110 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:18:14,110 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:18:14,118 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2024-11-19 21:18:14,313 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2024-11-19 21:18:14,314 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:18:14,314 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:18:14,314 INFO L85 PathProgramCache]: Analyzing trace with hash 798002477, now seen corresponding path program 2 times [2024-11-19 21:18:14,314 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:18:14,314 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [511858754] [2024-11-19 21:18:14,314 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:14,314 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:18:14,327 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:14,386 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-19 21:18:14,387 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:14,389 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-19 21:18:14,390 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:14,391 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-19 21:18:14,393 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:14,394 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-19 21:18:14,394 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:14,396 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-11-19 21:18:14,397 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:14,400 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 39 [2024-11-19 21:18:14,402 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:14,405 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 44 [2024-11-19 21:18:14,405 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:14,408 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 49 [2024-11-19 21:18:14,412 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:14,414 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 59 [2024-11-19 21:18:14,415 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:14,420 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 64 [2024-11-19 21:18:14,421 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:14,422 INFO L134 CoverageAnalysis]: Checked inductivity of 108 backedges. 20 proven. 0 refuted. 0 times theorem prover too weak. 88 trivial. 0 not checked. [2024-11-19 21:18:14,424 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:18:14,424 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [511858754] [2024-11-19 21:18:14,424 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [511858754] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 21:18:14,424 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-19 21:18:14,424 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-19 21:18:14,425 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [658756236] [2024-11-19 21:18:14,425 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 21:18:14,425 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-19 21:18:14,425 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:18:14,426 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-19 21:18:14,426 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-19 21:18:14,426 INFO L87 Difference]: Start difference. First operand 268 states and 375 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, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2024-11-19 21:18:14,574 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:18:14,575 INFO L93 Difference]: Finished difference Result 459 states and 645 transitions. [2024-11-19 21:18:14,575 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-19 21:18:14,575 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, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) Word has length 73 [2024-11-19 21:18:14,575 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:18:14,578 INFO L225 Difference]: With dead ends: 459 [2024-11-19 21:18:14,578 INFO L226 Difference]: Without dead ends: 289 [2024-11-19 21:18:14,580 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 26 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-19 21:18:14,581 INFO L432 NwaCegarLoop]: 37 mSDtfsCounter, 1 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 43 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 121 SdHoareTripleChecker+Invalid, 44 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 43 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-19 21:18:14,581 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 121 Invalid, 44 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 43 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-19 21:18:14,584 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 289 states. [2024-11-19 21:18:14,698 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 289 to 277. [2024-11-19 21:18:14,699 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 277 states, 168 states have (on average 1.1964285714285714) internal successors, (201), 169 states have internal predecessors, (201), 93 states have call successors, (93), 15 states have call predecessors, (93), 15 states have return successors, (92), 92 states have call predecessors, (92), 92 states have call successors, (92) [2024-11-19 21:18:14,700 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 277 states to 277 states and 386 transitions. [2024-11-19 21:18:14,701 INFO L78 Accepts]: Start accepts. Automaton has 277 states and 386 transitions. Word has length 73 [2024-11-19 21:18:14,701 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:18:14,701 INFO L471 AbstractCegarLoop]: Abstraction has 277 states and 386 transitions. [2024-11-19 21:18:14,701 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, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2024-11-19 21:18:14,702 INFO L276 IsEmpty]: Start isEmpty. Operand 277 states and 386 transitions. [2024-11-19 21:18:14,702 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2024-11-19 21:18:14,702 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:18:14,702 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 4, 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, 1, 1, 1, 1] [2024-11-19 21:18:14,703 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13 [2024-11-19 21:18:14,703 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:18:14,703 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:18:14,703 INFO L85 PathProgramCache]: Analyzing trace with hash -1622368081, now seen corresponding path program 3 times [2024-11-19 21:18:14,703 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:18:14,703 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1101177056] [2024-11-19 21:18:14,703 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:14,703 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:18:14,717 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:18:14,718 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1549165505] [2024-11-19 21:18:14,718 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-19 21:18:14,718 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:18:14,718 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:18:14,720 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:18:14,722 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-19 21:18:14,767 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-19 21:18:14,768 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 21:18:14,769 INFO L255 TraceCheckSpWp]: Trace formula consists of 154 conjuncts, 69 conjuncts are in the unsatisfiable core [2024-11-19 21:18:14,772 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:18:15,635 INFO L134 CoverageAnalysis]: Checked inductivity of 96 backedges. 27 proven. 26 refuted. 0 times theorem prover too weak. 43 trivial. 0 not checked. [2024-11-19 21:18:15,636 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 21:18:16,216 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:18:16,216 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1101177056] [2024-11-19 21:18:16,216 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-19 21:18:16,216 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1549165505] [2024-11-19 21:18:16,216 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1549165505] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 21:18:16,216 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-19 21:18:16,216 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19] total 19 [2024-11-19 21:18:16,216 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [453476348] [2024-11-19 21:18:16,216 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-19 21:18:16,217 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-19 21:18:16,217 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:18:16,217 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-19 21:18:16,218 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=115, Invalid=587, Unknown=0, NotChecked=0, Total=702 [2024-11-19 21:18:16,218 INFO L87 Difference]: Start difference. First operand 277 states and 386 transitions. Second operand has 19 states, 18 states have (on average 2.1666666666666665) internal successors, (39), 16 states have internal predecessors, (39), 5 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) [2024-11-19 21:18:16,916 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:18:16,917 INFO L93 Difference]: Finished difference Result 344 states and 469 transitions. [2024-11-19 21:18:16,917 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-11-19 21:18:16,917 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 18 states have (on average 2.1666666666666665) internal successors, (39), 16 states have internal predecessors, (39), 5 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) Word has length 73 [2024-11-19 21:18:16,918 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:18:16,920 INFO L225 Difference]: With dead ends: 344 [2024-11-19 21:18:16,920 INFO L226 Difference]: Without dead ends: 342 [2024-11-19 21:18:16,921 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 99 GetRequests, 67 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 230 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=189, Invalid=933, Unknown=0, NotChecked=0, Total=1122 [2024-11-19 21:18:16,921 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 63 mSDsluCounter, 391 mSDsCounter, 0 mSdLazyCounter, 611 mSolverCounterSat, 48 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 79 SdHoareTripleChecker+Valid, 429 SdHoareTripleChecker+Invalid, 659 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 48 IncrementalHoareTripleChecker+Valid, 611 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-19 21:18:16,921 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [79 Valid, 429 Invalid, 659 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [48 Valid, 611 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-19 21:18:16,922 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 342 states. [2024-11-19 21:18:17,030 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 342 to 332. [2024-11-19 21:18:17,031 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 332 states, 202 states have (on average 1.188118811881188) internal successors, (240), 203 states have internal predecessors, (240), 109 states have call successors, (109), 20 states have call predecessors, (109), 20 states have return successors, (108), 108 states have call predecessors, (108), 108 states have call successors, (108) [2024-11-19 21:18:17,032 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 332 states to 332 states and 457 transitions. [2024-11-19 21:18:17,033 INFO L78 Accepts]: Start accepts. Automaton has 332 states and 457 transitions. Word has length 73 [2024-11-19 21:18:17,033 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:18:17,033 INFO L471 AbstractCegarLoop]: Abstraction has 332 states and 457 transitions. [2024-11-19 21:18:17,034 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 18 states have (on average 2.1666666666666665) internal successors, (39), 16 states have internal predecessors, (39), 5 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) [2024-11-19 21:18:17,034 INFO L276 IsEmpty]: Start isEmpty. Operand 332 states and 457 transitions. [2024-11-19 21:18:17,035 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2024-11-19 21:18:17,035 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:18:17,035 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:18:17,042 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-11-19 21:18:17,238 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2024-11-19 21:18:17,239 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:18:17,239 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:18:17,239 INFO L85 PathProgramCache]: Analyzing trace with hash 160585404, now seen corresponding path program 1 times [2024-11-19 21:18:17,239 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:18:17,239 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1141763878] [2024-11-19 21:18:17,239 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:17,239 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:18:17,259 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:18:17,260 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1917099863] [2024-11-19 21:18:17,260 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:17,260 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:18:17,260 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:18:17,262 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:18:17,264 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-19 21:18:17,327 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:17,329 INFO L255 TraceCheckSpWp]: Trace formula consists of 215 conjuncts, 68 conjuncts are in the unsatisfiable core [2024-11-19 21:18:17,332 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:18:18,188 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 22 proven. 22 refuted. 0 times theorem prover too weak. 127 trivial. 0 not checked. [2024-11-19 21:18:18,188 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 21:18:18,779 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 16 proven. 19 refuted. 0 times theorem prover too weak. 136 trivial. 0 not checked. [2024-11-19 21:18:18,779 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:18:18,779 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1141763878] [2024-11-19 21:18:18,779 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-19 21:18:18,779 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1917099863] [2024-11-19 21:18:18,779 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1917099863] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 21:18:18,779 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-19 21:18:18,779 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 14] total 30 [2024-11-19 21:18:18,779 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2053228730] [2024-11-19 21:18:18,779 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-19 21:18:18,780 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2024-11-19 21:18:18,780 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:18:18,781 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2024-11-19 21:18:18,781 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=118, Invalid=752, Unknown=0, NotChecked=0, Total=870 [2024-11-19 21:18:18,781 INFO L87 Difference]: Start difference. First operand 332 states and 457 transitions. Second operand has 30 states, 28 states have (on average 2.0357142857142856) internal successors, (57), 27 states have internal predecessors, (57), 8 states have call successors, (23), 3 states have call predecessors, (23), 2 states have return successors, (22), 6 states have call predecessors, (22), 6 states have call successors, (22) [2024-11-19 21:18:26,469 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:18:26,470 INFO L93 Difference]: Finished difference Result 505 states and 721 transitions. [2024-11-19 21:18:26,471 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 64 states. [2024-11-19 21:18:26,471 INFO L78 Accepts]: Start accepts. Automaton has has 30 states, 28 states have (on average 2.0357142857142856) internal successors, (57), 27 states have internal predecessors, (57), 8 states have call successors, (23), 3 states have call predecessors, (23), 2 states have return successors, (22), 6 states have call predecessors, (22), 6 states have call successors, (22) Word has length 87 [2024-11-19 21:18:26,471 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:18:26,474 INFO L225 Difference]: With dead ends: 505 [2024-11-19 21:18:26,474 INFO L226 Difference]: Without dead ends: 497 [2024-11-19 21:18:26,476 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 227 GetRequests, 144 SyntacticMatches, 0 SemanticMatches, 83 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1863 ImplicationChecksByTransitivity, 5.0s TimeCoverageRelationStatistics Valid=1147, Invalid=5993, Unknown=0, NotChecked=0, Total=7140 [2024-11-19 21:18:26,477 INFO L432 NwaCegarLoop]: 53 mSDtfsCounter, 287 mSDsluCounter, 669 mSDsCounter, 0 mSdLazyCounter, 940 mSolverCounterSat, 263 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 287 SdHoareTripleChecker+Valid, 722 SdHoareTripleChecker+Invalid, 1203 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 263 IncrementalHoareTripleChecker+Valid, 940 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.9s IncrementalHoareTripleChecker+Time [2024-11-19 21:18:26,477 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [287 Valid, 722 Invalid, 1203 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [263 Valid, 940 Invalid, 0 Unknown, 0 Unchecked, 2.9s Time] [2024-11-19 21:18:26,478 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 497 states. [2024-11-19 21:18:26,663 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 497 to 395. [2024-11-19 21:18:26,663 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 395 states, 236 states have (on average 1.2076271186440677) internal successors, (285), 237 states have internal predecessors, (285), 137 states have call successors, (137), 21 states have call predecessors, (137), 21 states have return successors, (136), 136 states have call predecessors, (136), 136 states have call successors, (136) [2024-11-19 21:18:26,665 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 395 states to 395 states and 558 transitions. [2024-11-19 21:18:26,666 INFO L78 Accepts]: Start accepts. Automaton has 395 states and 558 transitions. Word has length 87 [2024-11-19 21:18:26,666 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:18:26,666 INFO L471 AbstractCegarLoop]: Abstraction has 395 states and 558 transitions. [2024-11-19 21:18:26,667 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 30 states, 28 states have (on average 2.0357142857142856) internal successors, (57), 27 states have internal predecessors, (57), 8 states have call successors, (23), 3 states have call predecessors, (23), 2 states have return successors, (22), 6 states have call predecessors, (22), 6 states have call successors, (22) [2024-11-19 21:18:26,667 INFO L276 IsEmpty]: Start isEmpty. Operand 395 states and 558 transitions. [2024-11-19 21:18:26,668 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2024-11-19 21:18:26,668 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:18:26,668 INFO L215 NwaCegarLoop]: trace histogram [11, 10, 10, 4, 4, 4, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:18:26,674 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2024-11-19 21:18:26,868 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2024-11-19 21:18:26,868 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:18:26,869 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:18:26,869 INFO L85 PathProgramCache]: Analyzing trace with hash -275231594, now seen corresponding path program 1 times [2024-11-19 21:18:26,869 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:18:26,869 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2142209413] [2024-11-19 21:18:26,869 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:26,869 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:18:26,885 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:18:26,886 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1968580834] [2024-11-19 21:18:26,886 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:26,886 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:18:26,886 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:18:26,890 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:18:26,892 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-11-19 21:18:26,942 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:26,948 INFO L255 TraceCheckSpWp]: Trace formula consists of 203 conjuncts, 32 conjuncts are in the unsatisfiable core [2024-11-19 21:18:26,950 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:18:27,267 INFO L134 CoverageAnalysis]: Checked inductivity of 240 backedges. 26 proven. 19 refuted. 0 times theorem prover too weak. 195 trivial. 0 not checked. [2024-11-19 21:18:27,267 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 21:18:27,543 INFO L134 CoverageAnalysis]: Checked inductivity of 240 backedges. 22 proven. 14 refuted. 0 times theorem prover too weak. 204 trivial. 0 not checked. [2024-11-19 21:18:27,543 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:18:27,543 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2142209413] [2024-11-19 21:18:27,543 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-19 21:18:27,544 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1968580834] [2024-11-19 21:18:27,544 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1968580834] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 21:18:27,544 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-19 21:18:27,544 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 10] total 22 [2024-11-19 21:18:27,544 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1107154011] [2024-11-19 21:18:27,544 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-19 21:18:27,545 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-11-19 21:18:27,545 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:18:27,545 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-19 21:18:27,545 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=89, Invalid=373, Unknown=0, NotChecked=0, Total=462 [2024-11-19 21:18:27,546 INFO L87 Difference]: Start difference. First operand 395 states and 558 transitions. Second operand has 22 states, 22 states have (on average 1.9545454545454546) internal successors, (43), 19 states have internal predecessors, (43), 8 states have call successors, (27), 3 states have call predecessors, (27), 2 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) [2024-11-19 21:18:29,105 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:18:29,105 INFO L93 Difference]: Finished difference Result 921 states and 1445 transitions. [2024-11-19 21:18:29,105 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2024-11-19 21:18:29,105 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 1.9545454545454546) internal successors, (43), 19 states have internal predecessors, (43), 8 states have call successors, (27), 3 states have call predecessors, (27), 2 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) Word has length 90 [2024-11-19 21:18:29,106 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:18:29,111 INFO L225 Difference]: With dead ends: 921 [2024-11-19 21:18:29,111 INFO L226 Difference]: Without dead ends: 919 [2024-11-19 21:18:29,112 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 206 GetRequests, 159 SyntacticMatches, 0 SemanticMatches, 47 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 561 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=528, Invalid=1824, Unknown=0, NotChecked=0, Total=2352 [2024-11-19 21:18:29,113 INFO L432 NwaCegarLoop]: 44 mSDtfsCounter, 135 mSDsluCounter, 474 mSDsCounter, 0 mSdLazyCounter, 502 mSolverCounterSat, 107 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 139 SdHoareTripleChecker+Valid, 518 SdHoareTripleChecker+Invalid, 609 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 107 IncrementalHoareTripleChecker+Valid, 502 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-11-19 21:18:29,113 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [139 Valid, 518 Invalid, 609 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [107 Valid, 502 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-11-19 21:18:29,114 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 919 states. [2024-11-19 21:18:29,581 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 919 to 753. [2024-11-19 21:18:29,582 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 753 states, 383 states have (on average 1.2898172323759791) internal successors, (494), 384 states have internal predecessors, (494), 345 states have call successors, (345), 24 states have call predecessors, (345), 24 states have return successors, (344), 344 states have call predecessors, (344), 344 states have call successors, (344) [2024-11-19 21:18:29,586 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 753 states to 753 states and 1183 transitions. [2024-11-19 21:18:29,587 INFO L78 Accepts]: Start accepts. Automaton has 753 states and 1183 transitions. Word has length 90 [2024-11-19 21:18:29,587 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:18:29,588 INFO L471 AbstractCegarLoop]: Abstraction has 753 states and 1183 transitions. [2024-11-19 21:18:29,588 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 1.9545454545454546) internal successors, (43), 19 states have internal predecessors, (43), 8 states have call successors, (27), 3 states have call predecessors, (27), 2 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) [2024-11-19 21:18:29,588 INFO L276 IsEmpty]: Start isEmpty. Operand 753 states and 1183 transitions. [2024-11-19 21:18:29,589 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2024-11-19 21:18:29,589 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:18:29,589 INFO L215 NwaCegarLoop]: trace histogram [10, 9, 9, 4, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:18:29,598 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2024-11-19 21:18:29,791 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2024-11-19 21:18:29,792 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:18:29,792 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:18:29,792 INFO L85 PathProgramCache]: Analyzing trace with hash 1599365144, now seen corresponding path program 1 times [2024-11-19 21:18:29,792 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:18:29,792 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2059042870] [2024-11-19 21:18:29,792 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:29,792 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:18:29,811 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:18:29,812 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [966215712] [2024-11-19 21:18:29,812 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:29,812 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:18:29,812 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:18:29,815 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:18:29,818 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2024-11-19 21:18:29,870 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:29,876 INFO L255 TraceCheckSpWp]: Trace formula consists of 214 conjuncts, 47 conjuncts are in the unsatisfiable core [2024-11-19 21:18:29,878 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:18:30,449 INFO L134 CoverageAnalysis]: Checked inductivity of 206 backedges. 24 proven. 23 refuted. 0 times theorem prover too weak. 159 trivial. 0 not checked. [2024-11-19 21:18:30,449 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 21:18:30,821 INFO L134 CoverageAnalysis]: Checked inductivity of 206 backedges. 18 proven. 20 refuted. 0 times theorem prover too weak. 168 trivial. 0 not checked. [2024-11-19 21:18:30,822 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:18:30,822 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2059042870] [2024-11-19 21:18:30,822 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-19 21:18:30,822 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [966215712] [2024-11-19 21:18:30,822 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [966215712] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 21:18:30,822 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-19 21:18:30,822 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 23 [2024-11-19 21:18:30,822 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [675828805] [2024-11-19 21:18:30,822 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-19 21:18:30,823 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-11-19 21:18:30,823 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:18:30,823 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-19 21:18:30,823 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=80, Invalid=426, Unknown=0, NotChecked=0, Total=506 [2024-11-19 21:18:30,824 INFO L87 Difference]: Start difference. First operand 753 states and 1183 transitions. Second operand has 23 states, 23 states have (on average 2.3043478260869565) internal successors, (53), 20 states have internal predecessors, (53), 8 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2024-11-19 21:18:34,470 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.28s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-19 21:18:38,277 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:18:38,277 INFO L93 Difference]: Finished difference Result 1047 states and 1647 transitions. [2024-11-19 21:18:38,278 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 44 states. [2024-11-19 21:18:38,278 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 2.3043478260869565) internal successors, (53), 20 states have internal predecessors, (53), 8 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) Word has length 90 [2024-11-19 21:18:38,278 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:18:38,284 INFO L225 Difference]: With dead ends: 1047 [2024-11-19 21:18:38,284 INFO L226 Difference]: Without dead ends: 1045 [2024-11-19 21:18:38,285 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 215 GetRequests, 157 SyntacticMatches, 0 SemanticMatches, 58 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 766 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=711, Invalid=2829, Unknown=0, NotChecked=0, Total=3540 [2024-11-19 21:18:38,285 INFO L432 NwaCegarLoop]: 52 mSDtfsCounter, 185 mSDsluCounter, 624 mSDsCounter, 0 mSdLazyCounter, 860 mSolverCounterSat, 173 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 185 SdHoareTripleChecker+Valid, 676 SdHoareTripleChecker+Invalid, 1033 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 173 IncrementalHoareTripleChecker+Valid, 860 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.9s IncrementalHoareTripleChecker+Time [2024-11-19 21:18:38,286 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [185 Valid, 676 Invalid, 1033 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [173 Valid, 860 Invalid, 0 Unknown, 0 Unchecked, 3.9s Time] [2024-11-19 21:18:38,287 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1045 states. [2024-11-19 21:18:39,057 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1045 to 958. [2024-11-19 21:18:39,058 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 958 states, 488 states have (on average 1.3012295081967213) internal successors, (635), 489 states have internal predecessors, (635), 441 states have call successors, (441), 28 states have call predecessors, (441), 28 states have return successors, (440), 440 states have call predecessors, (440), 440 states have call successors, (440) [2024-11-19 21:18:39,062 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 958 states to 958 states and 1516 transitions. [2024-11-19 21:18:39,063 INFO L78 Accepts]: Start accepts. Automaton has 958 states and 1516 transitions. Word has length 90 [2024-11-19 21:18:39,063 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:18:39,064 INFO L471 AbstractCegarLoop]: Abstraction has 958 states and 1516 transitions. [2024-11-19 21:18:39,064 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 2.3043478260869565) internal successors, (53), 20 states have internal predecessors, (53), 8 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2024-11-19 21:18:39,064 INFO L276 IsEmpty]: Start isEmpty. Operand 958 states and 1516 transitions. [2024-11-19 21:18:39,065 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 96 [2024-11-19 21:18:39,065 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:18:39,065 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 5, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:18:39,072 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2024-11-19 21:18:39,266 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable17,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:18:39,266 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:18:39,266 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:18:39,266 INFO L85 PathProgramCache]: Analyzing trace with hash -1330396859, now seen corresponding path program 2 times [2024-11-19 21:18:39,266 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:18:39,266 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1945290641] [2024-11-19 21:18:39,266 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:39,267 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:18:39,278 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:39,448 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-19 21:18:39,449 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:39,450 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-19 21:18:39,451 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:39,452 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-19 21:18:39,452 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:39,453 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-19 21:18:39,453 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:39,454 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-11-19 21:18:39,455 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:39,457 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 39 [2024-11-19 21:18:39,458 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:39,460 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 44 [2024-11-19 21:18:39,460 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:39,462 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 49 [2024-11-19 21:18:39,463 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:39,464 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 64 [2024-11-19 21:18:39,465 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:39,466 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 69 [2024-11-19 21:18:39,467 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:39,469 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 74 [2024-11-19 21:18:39,469 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:39,471 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 79 [2024-11-19 21:18:39,472 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:18:39,473 INFO L134 CoverageAnalysis]: Checked inductivity of 194 backedges. 38 proven. 16 refuted. 0 times theorem prover too weak. 140 trivial. 0 not checked. [2024-11-19 21:18:39,474 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:18:39,474 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1945290641] [2024-11-19 21:18:39,474 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1945290641] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 21:18:39,474 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [696986478] [2024-11-19 21:18:39,474 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 21:18:39,474 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:18:39,474 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:18:39,477 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:18:39,480 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2024-11-19 21:18:39,537 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-19 21:18:39,538 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 21:18:39,539 INFO L255 TraceCheckSpWp]: Trace formula consists of 241 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-19 21:18:39,540 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:18:39,595 INFO L134 CoverageAnalysis]: Checked inductivity of 194 backedges. 38 proven. 16 refuted. 0 times theorem prover too weak. 140 trivial. 0 not checked. [2024-11-19 21:18:39,595 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 21:18:39,712 INFO L134 CoverageAnalysis]: Checked inductivity of 194 backedges. 38 proven. 16 refuted. 0 times theorem prover too weak. 140 trivial. 0 not checked. [2024-11-19 21:18:39,713 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [696986478] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 21:18:39,713 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 21:18:39,713 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10, 10] total 11 [2024-11-19 21:18:39,713 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2069037287] [2024-11-19 21:18:39,713 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 21:18:39,714 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-11-19 21:18:39,714 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:18:39,714 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-19 21:18:39,714 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=89, Unknown=0, NotChecked=0, Total=110 [2024-11-19 21:18:39,715 INFO L87 Difference]: Start difference. First operand 958 states and 1516 transitions. Second operand has 11 states, 11 states have (on average 3.5454545454545454) internal successors, (39), 11 states have internal predecessors, (39), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2024-11-19 21:18:40,869 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:18:40,869 INFO L93 Difference]: Finished difference Result 1072 states and 1687 transitions. [2024-11-19 21:18:40,870 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2024-11-19 21:18:40,870 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 3.5454545454545454) internal successors, (39), 11 states have internal predecessors, (39), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) Word has length 95 [2024-11-19 21:18:40,870 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:18:40,877 INFO L225 Difference]: With dead ends: 1072 [2024-11-19 21:18:40,877 INFO L226 Difference]: Without dead ends: 1065 [2024-11-19 21:18:40,877 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 242 GetRequests, 211 SyntacticMatches, 8 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 96 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=141, Invalid=459, Unknown=0, NotChecked=0, Total=600 [2024-11-19 21:18:40,878 INFO L432 NwaCegarLoop]: 59 mSDtfsCounter, 66 mSDsluCounter, 334 mSDsCounter, 0 mSdLazyCounter, 269 mSolverCounterSat, 57 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 70 SdHoareTripleChecker+Valid, 393 SdHoareTripleChecker+Invalid, 326 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 57 IncrementalHoareTripleChecker+Valid, 269 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-19 21:18:40,878 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [70 Valid, 393 Invalid, 326 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [57 Valid, 269 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-19 21:18:40,879 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1065 states. [2024-11-19 21:18:41,717 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1065 to 927. [2024-11-19 21:18:41,719 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 927 states, 465 states have (on average 1.3075268817204302) internal successors, (608), 466 states have internal predecessors, (608), 433 states have call successors, (433), 28 states have call predecessors, (433), 28 states have return successors, (432), 432 states have call predecessors, (432), 432 states have call successors, (432) [2024-11-19 21:18:41,723 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 927 states to 927 states and 1473 transitions. [2024-11-19 21:18:41,725 INFO L78 Accepts]: Start accepts. Automaton has 927 states and 1473 transitions. Word has length 95 [2024-11-19 21:18:41,725 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:18:41,725 INFO L471 AbstractCegarLoop]: Abstraction has 927 states and 1473 transitions. [2024-11-19 21:18:41,725 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 3.5454545454545454) internal successors, (39), 11 states have internal predecessors, (39), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2024-11-19 21:18:41,725 INFO L276 IsEmpty]: Start isEmpty. Operand 927 states and 1473 transitions. [2024-11-19 21:18:41,726 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 99 [2024-11-19 21:18:41,726 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:18:41,726 INFO L215 NwaCegarLoop]: trace histogram [10, 9, 9, 5, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:18:41,735 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Ended with exit code 0 [2024-11-19 21:18:41,927 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:18:41,927 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:18:41,928 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:18:41,928 INFO L85 PathProgramCache]: Analyzing trace with hash -577787487, now seen corresponding path program 4 times [2024-11-19 21:18:41,928 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:18:41,928 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [44814015] [2024-11-19 21:18:41,928 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:41,928 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:18:41,946 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:18:41,947 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1941129774] [2024-11-19 21:18:41,948 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-19 21:18:41,948 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:18:41,948 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:18:41,950 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:18:41,953 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2024-11-19 21:18:42,019 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-19 21:18:42,019 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 21:18:42,022 INFO L255 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 60 conjuncts are in the unsatisfiable core [2024-11-19 21:18:42,024 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:18:42,748 INFO L134 CoverageAnalysis]: Checked inductivity of 226 backedges. 18 proven. 40 refuted. 0 times theorem prover too weak. 168 trivial. 0 not checked. [2024-11-19 21:18:42,749 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 21:18:43,563 INFO L134 CoverageAnalysis]: Checked inductivity of 226 backedges. 20 proven. 38 refuted. 0 times theorem prover too weak. 168 trivial. 0 not checked. [2024-11-19 21:18:43,563 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:18:43,563 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [44814015] [2024-11-19 21:18:43,563 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-19 21:18:43,563 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1941129774] [2024-11-19 21:18:43,563 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1941129774] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 21:18:43,563 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-19 21:18:43,563 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 16] total 27 [2024-11-19 21:18:43,564 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [528198723] [2024-11-19 21:18:43,564 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-19 21:18:43,564 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2024-11-19 21:18:43,564 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:18:43,565 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2024-11-19 21:18:43,565 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=112, Invalid=590, Unknown=0, NotChecked=0, Total=702 [2024-11-19 21:18:43,565 INFO L87 Difference]: Start difference. First operand 927 states and 1473 transitions. Second operand has 27 states, 27 states have (on average 2.3703703703703702) internal successors, (64), 26 states have internal predecessors, (64), 7 states have call successors, (24), 2 states have call predecessors, (24), 1 states have return successors, (22), 7 states have call predecessors, (22), 7 states have call successors, (22) [2024-11-19 21:18:52,649 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:18:52,649 INFO L93 Difference]: Finished difference Result 1222 states and 1919 transitions. [2024-11-19 21:18:52,649 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2024-11-19 21:18:52,649 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 27 states have (on average 2.3703703703703702) internal successors, (64), 26 states have internal predecessors, (64), 7 states have call successors, (24), 2 states have call predecessors, (24), 1 states have return successors, (22), 7 states have call predecessors, (22), 7 states have call successors, (22) Word has length 98 [2024-11-19 21:18:52,650 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:18:52,657 INFO L225 Difference]: With dead ends: 1222 [2024-11-19 21:18:52,657 INFO L226 Difference]: Without dead ends: 1220 [2024-11-19 21:18:52,658 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 229 GetRequests, 166 SyntacticMatches, 3 SemanticMatches, 60 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 792 ImplicationChecksByTransitivity, 6.9s TimeCoverageRelationStatistics Valid=764, Invalid=3018, Unknown=0, NotChecked=0, Total=3782 [2024-11-19 21:18:52,659 INFO L432 NwaCegarLoop]: 46 mSDtfsCounter, 179 mSDsluCounter, 497 mSDsCounter, 0 mSdLazyCounter, 622 mSolverCounterSat, 202 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 183 SdHoareTripleChecker+Valid, 543 SdHoareTripleChecker+Invalid, 824 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 202 IncrementalHoareTripleChecker+Valid, 622 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.8s IncrementalHoareTripleChecker+Time [2024-11-19 21:18:52,659 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [183 Valid, 543 Invalid, 824 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [202 Valid, 622 Invalid, 0 Unknown, 0 Unchecked, 1.8s Time] [2024-11-19 21:18:52,660 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1220 states. [2024-11-19 21:18:53,730 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1220 to 1113. [2024-11-19 21:18:53,733 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1113 states, 563 states have (on average 1.3019538188277087) internal successors, (733), 564 states have internal predecessors, (733), 513 states have call successors, (513), 36 states have call predecessors, (513), 36 states have return successors, (512), 512 states have call predecessors, (512), 512 states have call successors, (512) [2024-11-19 21:18:53,738 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1113 states to 1113 states and 1758 transitions. [2024-11-19 21:18:53,740 INFO L78 Accepts]: Start accepts. Automaton has 1113 states and 1758 transitions. Word has length 98 [2024-11-19 21:18:53,740 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:18:53,741 INFO L471 AbstractCegarLoop]: Abstraction has 1113 states and 1758 transitions. [2024-11-19 21:18:53,741 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 27 states have (on average 2.3703703703703702) internal successors, (64), 26 states have internal predecessors, (64), 7 states have call successors, (24), 2 states have call predecessors, (24), 1 states have return successors, (22), 7 states have call predecessors, (22), 7 states have call successors, (22) [2024-11-19 21:18:53,741 INFO L276 IsEmpty]: Start isEmpty. Operand 1113 states and 1758 transitions. [2024-11-19 21:18:53,742 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 105 [2024-11-19 21:18:53,743 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:18:53,743 INFO L215 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 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-11-19 21:18:53,751 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2024-11-19 21:18:53,946 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:18:53,947 INFO L396 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:18:53,947 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:18:53,947 INFO L85 PathProgramCache]: Analyzing trace with hash 1084123749, now seen corresponding path program 2 times [2024-11-19 21:18:53,947 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:18:53,947 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [342871629] [2024-11-19 21:18:53,947 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:18:53,947 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:18:53,965 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:18:53,966 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1649901366] [2024-11-19 21:18:53,966 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 21:18:53,966 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:18:53,966 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:18:53,969 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:18:53,971 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2024-11-19 21:18:54,022 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-19 21:18:54,022 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 21:18:54,023 INFO L255 TraceCheckSpWp]: Trace formula consists of 237 conjuncts, 51 conjuncts are in the unsatisfiable core [2024-11-19 21:18:54,025 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:18:54,653 INFO L134 CoverageAnalysis]: Checked inductivity of 334 backedges. 24 proven. 22 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2024-11-19 21:18:54,654 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 21:18:55,175 INFO L134 CoverageAnalysis]: Checked inductivity of 334 backedges. 24 proven. 22 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2024-11-19 21:18:55,175 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:18:55,175 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [342871629] [2024-11-19 21:18:55,176 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-19 21:18:55,176 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1649901366] [2024-11-19 21:18:55,176 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1649901366] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 21:18:55,176 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-19 21:18:55,176 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 22 [2024-11-19 21:18:55,176 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1262604670] [2024-11-19 21:18:55,176 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-19 21:18:55,176 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-11-19 21:18:55,177 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:18:55,177 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-19 21:18:55,177 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=81, Invalid=381, Unknown=0, NotChecked=0, Total=462 [2024-11-19 21:18:55,177 INFO L87 Difference]: Start difference. First operand 1113 states and 1758 transitions. Second operand has 22 states, 20 states have (on average 2.3) internal successors, (46), 21 states have internal predecessors, (46), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) [2024-11-19 21:19:01,345 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:19:01,346 INFO L93 Difference]: Finished difference Result 1301 states and 2032 transitions. [2024-11-19 21:19:01,346 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 55 states. [2024-11-19 21:19:01,346 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 20 states have (on average 2.3) internal successors, (46), 21 states have internal predecessors, (46), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) Word has length 104 [2024-11-19 21:19:01,347 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:19:01,353 INFO L225 Difference]: With dead ends: 1301 [2024-11-19 21:19:01,353 INFO L226 Difference]: Without dead ends: 1293 [2024-11-19 21:19:01,354 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 253 GetRequests, 184 SyntacticMatches, 2 SemanticMatches, 67 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1249 ImplicationChecksByTransitivity, 3.4s TimeCoverageRelationStatistics Valid=994, Invalid=3698, Unknown=0, NotChecked=0, Total=4692 [2024-11-19 21:19:01,355 INFO L432 NwaCegarLoop]: 68 mSDtfsCounter, 201 mSDsluCounter, 602 mSDsCounter, 0 mSdLazyCounter, 915 mSolverCounterSat, 209 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 201 SdHoareTripleChecker+Valid, 670 SdHoareTripleChecker+Invalid, 1124 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 209 IncrementalHoareTripleChecker+Valid, 915 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.9s IncrementalHoareTripleChecker+Time [2024-11-19 21:19:01,355 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [201 Valid, 670 Invalid, 1124 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [209 Valid, 915 Invalid, 0 Unknown, 0 Unchecked, 1.9s Time] [2024-11-19 21:19:01,356 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1293 states. [2024-11-19 21:19:02,618 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1293 to 1267. [2024-11-19 21:19:02,620 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1267 states, 648 states have (on average 1.2993827160493827) internal successors, (842), 649 states have internal predecessors, (842), 577 states have call successors, (577), 41 states have call predecessors, (577), 41 states have return successors, (576), 576 states have call predecessors, (576), 576 states have call successors, (576) [2024-11-19 21:19:02,625 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1267 states to 1267 states and 1995 transitions. [2024-11-19 21:19:02,627 INFO L78 Accepts]: Start accepts. Automaton has 1267 states and 1995 transitions. Word has length 104 [2024-11-19 21:19:02,628 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:19:02,628 INFO L471 AbstractCegarLoop]: Abstraction has 1267 states and 1995 transitions. [2024-11-19 21:19:02,628 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 20 states have (on average 2.3) internal successors, (46), 21 states have internal predecessors, (46), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) [2024-11-19 21:19:02,628 INFO L276 IsEmpty]: Start isEmpty. Operand 1267 states and 1995 transitions. [2024-11-19 21:19:02,629 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2024-11-19 21:19:02,630 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:19:02,630 INFO L215 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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-11-19 21:19:02,638 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2024-11-19 21:19:02,830 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20,18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:19:02,830 INFO L396 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:19:02,831 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:19:02,831 INFO L85 PathProgramCache]: Analyzing trace with hash 2024025072, now seen corresponding path program 3 times [2024-11-19 21:19:02,831 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:19:02,831 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [172632239] [2024-11-19 21:19:02,831 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:19:02,831 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:19:02,846 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:19:02,847 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1404393026] [2024-11-19 21:19:02,847 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-19 21:19:02,847 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:19:02,847 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:19:02,854 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:19:02,857 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2024-11-19 21:19:02,919 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2024-11-19 21:19:02,919 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 21:19:02,921 INFO L255 TraceCheckSpWp]: Trace formula consists of 189 conjuncts, 53 conjuncts are in the unsatisfiable core [2024-11-19 21:19:02,923 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:19:03,670 INFO L134 CoverageAnalysis]: Checked inductivity of 339 backedges. 24 proven. 27 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2024-11-19 21:19:03,670 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 21:19:04,243 INFO L134 CoverageAnalysis]: Checked inductivity of 339 backedges. 24 proven. 27 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2024-11-19 21:19:04,243 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:19:04,243 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [172632239] [2024-11-19 21:19:04,243 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-19 21:19:04,244 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1404393026] [2024-11-19 21:19:04,244 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1404393026] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 21:19:04,244 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-19 21:19:04,244 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 24 [2024-11-19 21:19:04,244 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1874415099] [2024-11-19 21:19:04,244 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-19 21:19:04,244 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2024-11-19 21:19:04,244 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:19:04,245 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2024-11-19 21:19:04,245 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=88, Invalid=464, Unknown=0, NotChecked=0, Total=552 [2024-11-19 21:19:04,245 INFO L87 Difference]: Start difference. First operand 1267 states and 1995 transitions. Second operand has 24 states, 22 states have (on average 2.3636363636363638) internal successors, (52), 23 states have internal predecessors, (52), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) [2024-11-19 21:19:10,058 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:19:10,059 INFO L93 Difference]: Finished difference Result 1505 states and 2369 transitions. [2024-11-19 21:19:10,061 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 58 states. [2024-11-19 21:19:10,062 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 22 states have (on average 2.3636363636363638) internal successors, (52), 23 states have internal predecessors, (52), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) Word has length 107 [2024-11-19 21:19:10,062 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:19:10,071 INFO L225 Difference]: With dead ends: 1505 [2024-11-19 21:19:10,071 INFO L226 Difference]: Without dead ends: 1497 [2024-11-19 21:19:10,073 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 262 GetRequests, 188 SyntacticMatches, 2 SemanticMatches, 72 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1471 ImplicationChecksByTransitivity, 3.7s TimeCoverageRelationStatistics Valid=975, Invalid=4427, Unknown=0, NotChecked=0, Total=5402 [2024-11-19 21:19:10,074 INFO L432 NwaCegarLoop]: 51 mSDtfsCounter, 215 mSDsluCounter, 556 mSDsCounter, 0 mSdLazyCounter, 806 mSolverCounterSat, 211 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 215 SdHoareTripleChecker+Valid, 607 SdHoareTripleChecker+Invalid, 1017 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 211 IncrementalHoareTripleChecker+Valid, 806 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2024-11-19 21:19:10,074 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [215 Valid, 607 Invalid, 1017 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [211 Valid, 806 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2024-11-19 21:19:10,075 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1497 states. [2024-11-19 21:19:11,404 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1497 to 1357. [2024-11-19 21:19:11,407 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1357 states, 689 states have (on average 1.3033381712626995) internal successors, (898), 690 states have internal predecessors, (898), 625 states have call successors, (625), 42 states have call predecessors, (625), 42 states have return successors, (624), 624 states have call predecessors, (624), 624 states have call successors, (624) [2024-11-19 21:19:11,413 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1357 states to 1357 states and 2147 transitions. [2024-11-19 21:19:11,415 INFO L78 Accepts]: Start accepts. Automaton has 1357 states and 2147 transitions. Word has length 107 [2024-11-19 21:19:11,415 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:19:11,416 INFO L471 AbstractCegarLoop]: Abstraction has 1357 states and 2147 transitions. [2024-11-19 21:19:11,416 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 22 states have (on average 2.3636363636363638) internal successors, (52), 23 states have internal predecessors, (52), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) [2024-11-19 21:19:11,416 INFO L276 IsEmpty]: Start isEmpty. Operand 1357 states and 2147 transitions. [2024-11-19 21:19:11,418 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 113 [2024-11-19 21:19:11,418 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:19:11,418 INFO L215 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:19:11,426 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Ended with exit code 0 [2024-11-19 21:19:11,621 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable21,19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:19:11,622 INFO L396 AbstractCegarLoop]: === Iteration 23 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:19:11,622 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:19:11,622 INFO L85 PathProgramCache]: Analyzing trace with hash 1666306094, now seen corresponding path program 4 times [2024-11-19 21:19:11,622 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:19:11,622 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1668227121] [2024-11-19 21:19:11,622 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:19:11,623 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:19:11,640 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:19:11,642 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [882072613] [2024-11-19 21:19:11,643 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-19 21:19:11,643 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:19:11,643 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:19:11,645 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:19:11,647 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2024-11-19 21:19:11,709 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-19 21:19:11,709 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 21:19:11,711 INFO L255 TraceCheckSpWp]: Trace formula consists of 232 conjuncts, 80 conjuncts are in the unsatisfiable core [2024-11-19 21:19:11,713 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:19:12,806 INFO L134 CoverageAnalysis]: Checked inductivity of 350 backedges. 30 proven. 41 refuted. 0 times theorem prover too weak. 279 trivial. 0 not checked. [2024-11-19 21:19:12,807 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 21:19:14,150 INFO L134 CoverageAnalysis]: Checked inductivity of 350 backedges. 24 proven. 38 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2024-11-19 21:19:14,150 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:19:14,150 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1668227121] [2024-11-19 21:19:14,150 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-19 21:19:14,150 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [882072613] [2024-11-19 21:19:14,150 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [882072613] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 21:19:14,150 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-19 21:19:14,150 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 17] total 35 [2024-11-19 21:19:14,151 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1449912888] [2024-11-19 21:19:14,151 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-19 21:19:14,151 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 35 states [2024-11-19 21:19:14,151 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:19:14,152 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2024-11-19 21:19:14,152 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=168, Invalid=1022, Unknown=0, NotChecked=0, Total=1190 [2024-11-19 21:19:14,153 INFO L87 Difference]: Start difference. First operand 1357 states and 2147 transitions. Second operand has 35 states, 33 states have (on average 2.0303030303030303) internal successors, (67), 32 states have internal predecessors, (67), 10 states have call successors, (31), 3 states have call predecessors, (31), 2 states have return successors, (30), 8 states have call predecessors, (30), 8 states have call successors, (30) [2024-11-19 21:19:28,040 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:19:28,040 INFO L93 Difference]: Finished difference Result 1624 states and 2535 transitions. [2024-11-19 21:19:28,041 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 89 states. [2024-11-19 21:19:28,041 INFO L78 Accepts]: Start accepts. Automaton has has 35 states, 33 states have (on average 2.0303030303030303) internal successors, (67), 32 states have internal predecessors, (67), 10 states have call successors, (31), 3 states have call predecessors, (31), 2 states have return successors, (30), 8 states have call predecessors, (30), 8 states have call successors, (30) Word has length 112 [2024-11-19 21:19:28,041 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:19:28,047 INFO L225 Difference]: With dead ends: 1624 [2024-11-19 21:19:28,048 INFO L226 Difference]: Without dead ends: 1616 [2024-11-19 21:19:28,050 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 301 GetRequests, 189 SyntacticMatches, 0 SemanticMatches, 112 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3669 ImplicationChecksByTransitivity, 9.7s TimeCoverageRelationStatistics Valid=2306, Invalid=10576, Unknown=0, NotChecked=0, Total=12882 [2024-11-19 21:19:28,051 INFO L432 NwaCegarLoop]: 56 mSDtfsCounter, 345 mSDsluCounter, 898 mSDsCounter, 0 mSdLazyCounter, 1544 mSolverCounterSat, 358 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 345 SdHoareTripleChecker+Valid, 954 SdHoareTripleChecker+Invalid, 1902 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 358 IncrementalHoareTripleChecker+Valid, 1544 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.5s IncrementalHoareTripleChecker+Time [2024-11-19 21:19:28,051 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [345 Valid, 954 Invalid, 1902 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [358 Valid, 1544 Invalid, 0 Unknown, 0 Unchecked, 3.5s Time] [2024-11-19 21:19:28,052 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1616 states. [2024-11-19 21:19:29,567 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1616 to 1449. [2024-11-19 21:19:29,569 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1449 states, 747 states have (on average 1.2931726907630523) internal successors, (966), 748 states have internal predecessors, (966), 653 states have call successors, (653), 48 states have call predecessors, (653), 48 states have return successors, (652), 652 states have call predecessors, (652), 652 states have call successors, (652) [2024-11-19 21:19:29,574 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1449 states to 1449 states and 2271 transitions. [2024-11-19 21:19:29,576 INFO L78 Accepts]: Start accepts. Automaton has 1449 states and 2271 transitions. Word has length 112 [2024-11-19 21:19:29,576 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:19:29,577 INFO L471 AbstractCegarLoop]: Abstraction has 1449 states and 2271 transitions. [2024-11-19 21:19:29,577 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 35 states, 33 states have (on average 2.0303030303030303) internal successors, (67), 32 states have internal predecessors, (67), 10 states have call successors, (31), 3 states have call predecessors, (31), 2 states have return successors, (30), 8 states have call predecessors, (30), 8 states have call successors, (30) [2024-11-19 21:19:29,577 INFO L276 IsEmpty]: Start isEmpty. Operand 1449 states and 2271 transitions. [2024-11-19 21:19:29,579 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 118 [2024-11-19 21:19:29,579 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:19:29,579 INFO L215 NwaCegarLoop]: trace histogram [14, 13, 13, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:19:29,587 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Forceful destruction successful, exit code 0 [2024-11-19 21:19:29,781 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable22,20 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:19:29,782 INFO L396 AbstractCegarLoop]: === Iteration 24 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:19:29,782 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:19:29,782 INFO L85 PathProgramCache]: Analyzing trace with hash -1454845263, now seen corresponding path program 2 times [2024-11-19 21:19:29,782 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:19:29,783 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1554031882] [2024-11-19 21:19:29,783 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:19:29,783 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:19:29,804 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:19:29,806 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [556236315] [2024-11-19 21:19:29,808 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 21:19:29,808 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:19:29,808 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:19:29,810 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 21:19:29,812 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2024-11-19 21:19:29,873 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-19 21:19:29,873 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 21:19:29,875 INFO L255 TraceCheckSpWp]: Trace formula consists of 276 conjuncts, 71 conjuncts are in the unsatisfiable core [2024-11-19 21:19:29,879 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:19:31,027 INFO L134 CoverageAnalysis]: Checked inductivity of 408 backedges. 58 proven. 59 refuted. 0 times theorem prover too weak. 291 trivial. 0 not checked. [2024-11-19 21:19:31,028 INFO L311 TraceCheckSpWp]: Computing backward predicates...