./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_valuebound100.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 3061b6dc Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_valuebound100.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 4ecd26f30dcf2e00e51585057257a3ebe53fdc2d12652276addf710ad43d7dfd --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.dk.eval-assert-order-craig-3061b6d-m [2024-11-18 13:29:24,008 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-18 13:29:24,077 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-18 13:29:24,083 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-18 13:29:24,085 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-18 13:29:24,122 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-18 13:29:24,125 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-18 13:29:24,126 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-18 13:29:24,126 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-18 13:29:24,129 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-18 13:29:24,129 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-18 13:29:24,129 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-18 13:29:24,130 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-18 13:29:24,130 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-18 13:29:24,132 INFO L153 SettingsManager]: * Use SBE=true [2024-11-18 13:29:24,133 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-18 13:29:24,133 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-18 13:29:24,133 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-18 13:29:24,134 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-18 13:29:24,134 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-18 13:29:24,134 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-18 13:29:24,135 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-18 13:29:24,135 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-18 13:29:24,136 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-18 13:29:24,136 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-18 13:29:24,136 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-18 13:29:24,136 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-18 13:29:24,137 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-18 13:29:24,137 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-18 13:29:24,137 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-18 13:29:24,138 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-18 13:29:24,138 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-18 13:29:24,138 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-18 13:29:24,138 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-18 13:29:24,139 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-18 13:29:24,139 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-18 13:29:24,152 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-18 13:29:24,153 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-18 13:29:24,153 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-18 13:29:24,153 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-18 13:29:24,153 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-18 13:29:24,155 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-18 13:29:24,155 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 -> 4ecd26f30dcf2e00e51585057257a3ebe53fdc2d12652276addf710ad43d7dfd [2024-11-18 13:29:24,485 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-18 13:29:24,510 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-18 13:29:24,513 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-18 13:29:24,515 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-18 13:29:24,515 INFO L274 PluginConnector]: CDTParser initialized [2024-11-18 13:29:24,516 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_valuebound100.c [2024-11-18 13:29:26,007 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-18 13:29:26,194 INFO L384 CDTParser]: Found 1 translation units. [2024-11-18 13:29:26,194 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_valuebound100.c [2024-11-18 13:29:26,201 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/02c72226d/bd487081e0b7413a8a371fb47a055dfa/FLAGaaa5df215 [2024-11-18 13:29:26,213 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/02c72226d/bd487081e0b7413a8a371fb47a055dfa [2024-11-18 13:29:26,215 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-18 13:29:26,216 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-18 13:29:26,218 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-18 13:29:26,218 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-18 13:29:26,222 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-18 13:29:26,222 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 18.11 01:29:26" (1/1) ... [2024-11-18 13:29:26,223 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@3c6d92c3 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:29:26, skipping insertion in model container [2024-11-18 13:29:26,223 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 18.11 01:29:26" (1/1) ... [2024-11-18 13:29:26,242 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-18 13:29:26,411 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/cohencu-ll_valuebound100.c[588,601] [2024-11-18 13:29:26,433 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-18 13:29:26,443 INFO L200 MainTranslator]: Completed pre-run [2024-11-18 13:29:26,455 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/cohencu-ll_valuebound100.c[588,601] [2024-11-18 13:29:26,467 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-18 13:29:26,483 INFO L204 MainTranslator]: Completed translation [2024-11-18 13:29:26,483 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:29:26 WrapperNode [2024-11-18 13:29:26,483 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-18 13:29:26,484 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-18 13:29:26,484 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-18 13:29:26,484 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-18 13:29:26,490 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:29:26" (1/1) ... [2024-11-18 13:29:26,499 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:29:26" (1/1) ... [2024-11-18 13:29:26,515 INFO L138 Inliner]: procedures = 14, calls = 19, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 48 [2024-11-18 13:29:26,516 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-18 13:29:26,517 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-18 13:29:26,517 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-18 13:29:26,517 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-18 13:29:26,526 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:29:26" (1/1) ... [2024-11-18 13:29:26,526 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:29:26" (1/1) ... [2024-11-18 13:29:26,528 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:29:26" (1/1) ... [2024-11-18 13:29:26,544 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-18 13:29:26,544 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:29:26" (1/1) ... [2024-11-18 13:29:26,544 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:29:26" (1/1) ... [2024-11-18 13:29:26,547 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:29:26" (1/1) ... [2024-11-18 13:29:26,551 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:29:26" (1/1) ... [2024-11-18 13:29:26,552 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:29:26" (1/1) ... [2024-11-18 13:29:26,553 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:29:26" (1/1) ... [2024-11-18 13:29:26,555 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-18 13:29:26,556 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-18 13:29:26,556 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-18 13:29:26,556 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-18 13:29:26,557 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:29:26" (1/1) ... [2024-11-18 13:29:26,562 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-18 13:29:26,573 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:29:26,590 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-18 13:29:26,594 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-18 13:29:26,644 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-18 13:29:26,645 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-18 13:29:26,645 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-18 13:29:26,645 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-18 13:29:26,645 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-18 13:29:26,645 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-18 13:29:26,710 INFO L238 CfgBuilder]: Building ICFG [2024-11-18 13:29:26,714 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-18 13:29:26,944 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-11-18 13:29:26,946 INFO L287 CfgBuilder]: Performing block encoding [2024-11-18 13:29:26,961 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-18 13:29:26,961 INFO L316 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-18 13:29:26,961 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.11 01:29:26 BoogieIcfgContainer [2024-11-18 13:29:26,962 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-18 13:29:26,965 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-18 13:29:26,965 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-18 13:29:26,968 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-18 13:29:26,968 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 18.11 01:29:26" (1/3) ... [2024-11-18 13:29:26,969 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@38b9677e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.11 01:29:26, skipping insertion in model container [2024-11-18 13:29:26,970 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:29:26" (2/3) ... [2024-11-18 13:29:26,970 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@38b9677e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.11 01:29:26, skipping insertion in model container [2024-11-18 13:29:26,971 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.11 01:29:26" (3/3) ... [2024-11-18 13:29:26,972 INFO L112 eAbstractionObserver]: Analyzing ICFG cohencu-ll_valuebound100.c [2024-11-18 13:29:26,990 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-18 13:29:26,990 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-18 13:29:27,057 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-18 13:29:27,065 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;@2939d2c1, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-18 13:29:27,065 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-18 13:29:27,070 INFO L276 IsEmpty]: Start isEmpty. Operand has 27 states, 13 states have (on average 1.4615384615384615) internal successors, (19), 14 states have internal predecessors, (19), 11 states have call successors, (11), 1 states have call predecessors, (11), 1 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-18 13:29:27,078 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2024-11-18 13:29:27,079 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:29:27,080 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:29:27,081 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:29:27,086 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:29:27,087 INFO L85 PathProgramCache]: Analyzing trace with hash -588951690, now seen corresponding path program 1 times [2024-11-18 13:29:27,096 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:29:27,097 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1816858968] [2024-11-18 13:29:27,098 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:29:27,098 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:29:27,202 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:29:27,249 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-18 13:29:27,250 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:29:27,250 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1816858968] [2024-11-18 13:29:27,251 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1816858968] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:29:27,251 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:29:27,251 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-18 13:29:27,253 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [104057559] [2024-11-18 13:29:27,254 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:29:27,258 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-18 13:29:27,258 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:29:27,278 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-18 13:29:27,279 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-18 13:29:27,281 INFO L87 Difference]: Start difference. First operand has 27 states, 13 states have (on average 1.4615384615384615) internal successors, (19), 14 states have internal predecessors, (19), 11 states have call successors, (11), 1 states have call predecessors, (11), 1 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-18 13:29:27,304 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:29:27,304 INFO L93 Difference]: Finished difference Result 51 states and 89 transitions. [2024-11-18 13:29:27,305 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-18 13:29:27,306 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2024-11-18 13:29:27,307 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:29:27,315 INFO L225 Difference]: With dead ends: 51 [2024-11-18 13:29:27,315 INFO L226 Difference]: Without dead ends: 23 [2024-11-18 13:29:27,321 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-18 13:29:27,326 INFO L432 NwaCegarLoop]: 37 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, 37 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-18 13:29:27,328 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:29:27,343 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2024-11-18 13:29:27,360 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2024-11-18 13:29:27,362 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 10 states have (on average 1.2) internal successors, (12), 11 states have internal predecessors, (12), 11 states have call successors, (11), 1 states have call predecessors, (11), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-18 13:29:27,363 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 33 transitions. [2024-11-18 13:29:27,366 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 33 transitions. Word has length 9 [2024-11-18 13:29:27,366 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:29:27,367 INFO L471 AbstractCegarLoop]: Abstraction has 23 states and 33 transitions. [2024-11-18 13:29:27,367 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-18 13:29:27,367 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 33 transitions. [2024-11-18 13:29:27,368 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2024-11-18 13:29:27,368 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:29:27,368 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:29:27,369 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-18 13:29:27,369 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:29:27,370 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:29:27,370 INFO L85 PathProgramCache]: Analyzing trace with hash 1187604804, now seen corresponding path program 1 times [2024-11-18 13:29:27,370 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:29:27,370 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1830472985] [2024-11-18 13:29:27,370 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:29:27,370 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:29:27,414 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:29:27,692 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-18 13:29:27,693 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:29:27,693 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1830472985] [2024-11-18 13:29:27,693 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1830472985] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:29:27,694 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:29:27,694 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-18 13:29:27,694 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1516889578] [2024-11-18 13:29:27,694 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:29:27,695 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:29:27,696 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:29:27,697 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:29:27,697 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-18 13:29:27,697 INFO L87 Difference]: Start difference. First operand 23 states and 33 transitions. Second operand has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-18 13:29:27,924 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:29:27,925 INFO L93 Difference]: Finished difference Result 29 states and 38 transitions. [2024-11-18 13:29:27,925 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-18 13:29:27,926 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2024-11-18 13:29:27,926 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:29:27,927 INFO L225 Difference]: With dead ends: 29 [2024-11-18 13:29:27,927 INFO L226 Difference]: Without dead ends: 27 [2024-11-18 13:29:27,927 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 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-18 13:29:27,930 INFO L432 NwaCegarLoop]: 27 mSDtfsCounter, 4 mSDsluCounter, 59 mSDsCounter, 0 mSdLazyCounter, 30 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 86 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 30 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-18 13:29:27,931 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 86 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 30 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-18 13:29:27,932 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2024-11-18 13:29:27,942 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2024-11-18 13:29:27,943 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 13 states have (on average 1.1538461538461537) internal successors, (15), 14 states have internal predecessors, (15), 11 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-18 13:29:27,944 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 36 transitions. [2024-11-18 13:29:27,945 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 36 transitions. Word has length 9 [2024-11-18 13:29:27,945 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:29:27,945 INFO L471 AbstractCegarLoop]: Abstraction has 27 states and 36 transitions. [2024-11-18 13:29:27,945 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-18 13:29:27,945 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 36 transitions. [2024-11-18 13:29:27,946 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2024-11-18 13:29:27,946 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:29:27,946 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:29:27,946 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-18 13:29:27,947 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:29:27,947 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:29:27,948 INFO L85 PathProgramCache]: Analyzing trace with hash 1137950087, now seen corresponding path program 1 times [2024-11-18 13:29:27,948 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:29:27,948 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [939859795] [2024-11-18 13:29:27,948 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:29:27,948 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:29:27,979 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:29:27,985 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1834715424] [2024-11-18 13:29:27,985 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:29:27,985 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:29:27,986 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:29:27,989 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-18 13:29:27,992 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-18 13:29:28,056 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:29:28,063 INFO L255 TraceCheckSpWp]: Trace formula consists of 55 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-18 13:29:28,070 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:29:28,164 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-18 13:29:28,165 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-18 13:29:28,165 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:29:28,165 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [939859795] [2024-11-18 13:29:28,166 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:29:28,166 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1834715424] [2024-11-18 13:29:28,167 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1834715424] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:29:28,167 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:29:28,167 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-18 13:29:28,167 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [384433731] [2024-11-18 13:29:28,167 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:29:28,168 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:29:28,168 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:29:28,169 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:29:28,170 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-18 13:29:28,170 INFO L87 Difference]: Start difference. First operand 27 states and 36 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-18 13:29:28,351 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:29:28,355 INFO L93 Difference]: Finished difference Result 46 states and 65 transitions. [2024-11-18 13:29:28,356 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-18 13:29:28,357 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 14 [2024-11-18 13:29:28,357 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:29:28,358 INFO L225 Difference]: With dead ends: 46 [2024-11-18 13:29:28,360 INFO L226 Difference]: Without dead ends: 44 [2024-11-18 13:29:28,361 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 10 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-18 13:29:28,363 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 4 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 107 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:29:28,364 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 107 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:29:28,365 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2024-11-18 13:29:28,384 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 34. [2024-11-18 13:29:28,385 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 17 states have (on average 1.1176470588235294) internal successors, (19), 19 states have internal predecessors, (19), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 11 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-18 13:29:28,386 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 44 transitions. [2024-11-18 13:29:28,389 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 44 transitions. Word has length 14 [2024-11-18 13:29:28,390 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:29:28,390 INFO L471 AbstractCegarLoop]: Abstraction has 34 states and 44 transitions. [2024-11-18 13:29:28,390 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-18 13:29:28,390 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 44 transitions. [2024-11-18 13:29:28,391 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2024-11-18 13:29:28,391 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:29:28,391 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:29:28,412 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-18 13:29:28,595 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-18 13:29:28,596 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:29:28,597 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:29:28,597 INFO L85 PathProgramCache]: Analyzing trace with hash -1500531996, now seen corresponding path program 1 times [2024-11-18 13:29:28,597 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:29:28,597 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [806788963] [2024-11-18 13:29:28,597 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:29:28,598 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:29:28,626 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:29:28,627 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [762844130] [2024-11-18 13:29:28,628 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:29:28,628 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:29:28,628 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:29:28,630 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-18 13:29:28,632 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-18 13:29:28,684 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:29:28,688 INFO L255 TraceCheckSpWp]: Trace formula consists of 64 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-18 13:29:28,690 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:29:28,759 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-18 13:29:28,760 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-18 13:29:28,760 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:29:28,760 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [806788963] [2024-11-18 13:29:28,762 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:29:28,762 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [762844130] [2024-11-18 13:29:28,762 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [762844130] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:29:28,762 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:29:28,763 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-18 13:29:28,763 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [810154962] [2024-11-18 13:29:28,763 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:29:28,763 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:29:28,767 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:29:28,768 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:29:28,768 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-18 13:29:28,768 INFO L87 Difference]: Start difference. First operand 34 states and 44 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-18 13:29:28,877 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:29:28,877 INFO L93 Difference]: Finished difference Result 50 states and 68 transitions. [2024-11-18 13:29:28,878 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-18 13:29:28,878 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 19 [2024-11-18 13:29:28,879 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:29:28,880 INFO L225 Difference]: With dead ends: 50 [2024-11-18 13:29:28,880 INFO L226 Difference]: Without dead ends: 48 [2024-11-18 13:29:28,881 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 15 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-18 13:29:28,882 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 4 mSDsluCounter, 74 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 104 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:29:28,882 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 104 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:29:28,883 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2024-11-18 13:29:28,895 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 44. [2024-11-18 13:29:28,896 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 21 states have (on average 1.1428571428571428) internal successors, (24), 23 states have internal predecessors, (24), 18 states have call successors, (18), 4 states have call predecessors, (18), 4 states have return successors, (17), 16 states have call predecessors, (17), 17 states have call successors, (17) [2024-11-18 13:29:28,898 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 59 transitions. [2024-11-18 13:29:28,900 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 59 transitions. Word has length 19 [2024-11-18 13:29:28,901 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:29:28,901 INFO L471 AbstractCegarLoop]: Abstraction has 44 states and 59 transitions. [2024-11-18 13:29:28,901 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-18 13:29:28,902 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 59 transitions. [2024-11-18 13:29:28,903 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2024-11-18 13:29:28,904 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:29:28,904 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:29:28,923 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-18 13:29:29,105 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-18 13:29:29,106 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:29:29,107 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:29:29,107 INFO L85 PathProgramCache]: Analyzing trace with hash 1926539111, now seen corresponding path program 1 times [2024-11-18 13:29:29,107 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:29:29,107 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [87587277] [2024-11-18 13:29:29,108 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:29:29,108 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:29:29,140 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:29:29,142 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1139555395] [2024-11-18 13:29:29,142 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:29:29,142 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:29:29,145 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:29:29,147 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-18 13:29:29,148 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-18 13:29:29,206 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:29:29,215 INFO L255 TraceCheckSpWp]: Trace formula consists of 73 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-18 13:29:29,217 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:29:29,322 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-18 13:29:29,323 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-18 13:29:29,323 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:29:29,323 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [87587277] [2024-11-18 13:29:29,323 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:29:29,323 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1139555395] [2024-11-18 13:29:29,324 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1139555395] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:29:29,324 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:29:29,324 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-18 13:29:29,324 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1559024338] [2024-11-18 13:29:29,324 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:29:29,325 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:29:29,325 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:29:29,325 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:29:29,326 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-18 13:29:29,326 INFO L87 Difference]: Start difference. First operand 44 states and 59 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-18 13:29:29,420 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:29:29,420 INFO L93 Difference]: Finished difference Result 58 states and 74 transitions. [2024-11-18 13:29:29,421 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-18 13:29:29,421 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 24 [2024-11-18 13:29:29,421 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:29:29,422 INFO L225 Difference]: With dead ends: 58 [2024-11-18 13:29:29,423 INFO L226 Difference]: Without dead ends: 46 [2024-11-18 13:29:29,424 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 20 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-18 13:29:29,425 INFO L432 NwaCegarLoop]: 27 mSDtfsCounter, 4 mSDsluCounter, 69 mSDsCounter, 0 mSdLazyCounter, 43 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 96 SdHoareTripleChecker+Invalid, 49 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 43 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:29:29,425 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 96 Invalid, 49 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 43 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:29:29,426 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2024-11-18 13:29:29,441 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 46. [2024-11-18 13:29:29,442 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 24 states have (on average 1.0833333333333333) internal successors, (26), 25 states have internal predecessors, (26), 16 states have call successors, (16), 5 states have call predecessors, (16), 5 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2024-11-18 13:29:29,443 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 57 transitions. [2024-11-18 13:29:29,446 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 57 transitions. Word has length 24 [2024-11-18 13:29:29,447 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:29:29,447 INFO L471 AbstractCegarLoop]: Abstraction has 46 states and 57 transitions. [2024-11-18 13:29:29,447 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-18 13:29:29,447 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 57 transitions. [2024-11-18 13:29:29,448 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2024-11-18 13:29:29,448 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:29:29,448 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:29:29,468 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-18 13:29:29,649 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-18 13:29:29,649 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:29:29,650 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:29:29,650 INFO L85 PathProgramCache]: Analyzing trace with hash -492592860, now seen corresponding path program 1 times [2024-11-18 13:29:29,650 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:29:29,650 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [28075655] [2024-11-18 13:29:29,650 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:29:29,650 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:29:29,680 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:29:29,682 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [299977632] [2024-11-18 13:29:29,683 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:29:29,683 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:29:29,683 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:29:29,686 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-18 13:29:29,687 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-18 13:29:29,738 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:29:29,739 INFO L255 TraceCheckSpWp]: Trace formula consists of 110 conjuncts, 23 conjuncts are in the unsatisfiable core [2024-11-18 13:29:29,742 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:29:29,885 INFO L134 CoverageAnalysis]: Checked inductivity of 75 backedges. 11 proven. 19 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-18 13:29:29,887 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:29:30,076 INFO L134 CoverageAnalysis]: Checked inductivity of 75 backedges. 13 proven. 17 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-18 13:29:30,077 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:29:30,077 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [28075655] [2024-11-18 13:29:30,077 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:29:30,077 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [299977632] [2024-11-18 13:29:30,078 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [299977632] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:29:30,078 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:29:30,078 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2024-11-18 13:29:30,078 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1919467771] [2024-11-18 13:29:30,078 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:29:30,079 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-18 13:29:30,079 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:29:30,079 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-18 13:29:30,080 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=121, Unknown=0, NotChecked=0, Total=156 [2024-11-18 13:29:30,080 INFO L87 Difference]: Start difference. First operand 46 states and 57 transitions. Second operand has 13 states, 13 states have (on average 1.8461538461538463) internal successors, (24), 11 states have internal predecessors, (24), 5 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 5 states have call successors, (12) [2024-11-18 13:29:30,381 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:29:30,381 INFO L93 Difference]: Finished difference Result 69 states and 89 transitions. [2024-11-18 13:29:30,382 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-18 13:29:30,382 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 1.8461538461538463) internal successors, (24), 11 states have internal predecessors, (24), 5 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 5 states have call successors, (12) Word has length 41 [2024-11-18 13:29:30,382 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:29:30,383 INFO L225 Difference]: With dead ends: 69 [2024-11-18 13:29:30,383 INFO L226 Difference]: Without dead ends: 67 [2024-11-18 13:29:30,384 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 83 GetRequests, 69 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=56, Invalid=184, Unknown=0, NotChecked=0, Total=240 [2024-11-18 13:29:30,385 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 10 mSDsluCounter, 129 mSDsCounter, 0 mSdLazyCounter, 176 mSolverCounterSat, 53 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 153 SdHoareTripleChecker+Invalid, 229 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 53 IncrementalHoareTripleChecker+Valid, 176 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-18 13:29:30,385 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 153 Invalid, 229 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [53 Valid, 176 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-18 13:29:30,386 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2024-11-18 13:29:30,406 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 54. [2024-11-18 13:29:30,406 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 30 states have (on average 1.0666666666666667) internal successors, (32), 31 states have internal predecessors, (32), 16 states have call successors, (16), 7 states have call predecessors, (16), 7 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2024-11-18 13:29:30,408 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 63 transitions. [2024-11-18 13:29:30,409 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 63 transitions. Word has length 41 [2024-11-18 13:29:30,410 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:29:30,411 INFO L471 AbstractCegarLoop]: Abstraction has 54 states and 63 transitions. [2024-11-18 13:29:30,411 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 1.8461538461538463) internal successors, (24), 11 states have internal predecessors, (24), 5 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 5 states have call successors, (12) [2024-11-18 13:29:30,411 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 63 transitions. [2024-11-18 13:29:30,412 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2024-11-18 13:29:30,412 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:29:30,413 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:29:30,431 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-18 13:29:30,616 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-18 13:29:30,616 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:29:30,616 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:29:30,616 INFO L85 PathProgramCache]: Analyzing trace with hash 1495173479, now seen corresponding path program 2 times [2024-11-18 13:29:30,617 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:29:30,617 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [928460418] [2024-11-18 13:29:30,617 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:29:30,617 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:29:30,647 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:29:30,647 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:29:30,649 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1437597927] [2024-11-18 13:29:30,649 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:29:30,649 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:29:30,649 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:29:30,651 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-18 13:29:30,653 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-18 13:29:30,707 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:29:30,707 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:29:30,708 INFO L255 TraceCheckSpWp]: Trace formula consists of 119 conjuncts, 25 conjuncts are in the unsatisfiable core [2024-11-18 13:29:30,710 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:29:30,834 INFO L134 CoverageAnalysis]: Checked inductivity of 102 backedges. 13 proven. 23 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2024-11-18 13:29:30,834 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:29:30,984 INFO L134 CoverageAnalysis]: Checked inductivity of 102 backedges. 13 proven. 23 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2024-11-18 13:29:30,985 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:29:30,985 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [928460418] [2024-11-18 13:29:30,985 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:29:30,986 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1437597927] [2024-11-18 13:29:30,986 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1437597927] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:29:30,986 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:29:30,986 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2024-11-18 13:29:30,986 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [172354880] [2024-11-18 13:29:30,986 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:29:30,988 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-18 13:29:30,988 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:29:30,989 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-18 13:29:30,989 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=123, Unknown=0, NotChecked=0, Total=156 [2024-11-18 13:29:30,990 INFO L87 Difference]: Start difference. First operand 54 states and 63 transitions. Second operand has 13 states, 13 states have (on average 1.8461538461538463) internal successors, (24), 11 states have internal predecessors, (24), 5 states have call successors, (16), 3 states have call predecessors, (16), 2 states have return successors, (14), 4 states have call predecessors, (14), 5 states have call successors, (14) [2024-11-18 13:29:35,290 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.03s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-18 13:29:35,338 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:29:35,338 INFO L93 Difference]: Finished difference Result 84 states and 103 transitions. [2024-11-18 13:29:35,343 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-18 13:29:35,343 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 1.8461538461538463) internal successors, (24), 11 states have internal predecessors, (24), 5 states have call successors, (16), 3 states have call predecessors, (16), 2 states have return successors, (14), 4 states have call predecessors, (14), 5 states have call successors, (14) Word has length 46 [2024-11-18 13:29:35,343 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:29:35,346 INFO L225 Difference]: With dead ends: 84 [2024-11-18 13:29:35,346 INFO L226 Difference]: Without dead ends: 82 [2024-11-18 13:29:35,346 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 94 GetRequests, 79 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=61, Invalid=211, Unknown=0, NotChecked=0, Total=272 [2024-11-18 13:29:35,347 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 10 mSDsluCounter, 104 mSDsCounter, 0 mSdLazyCounter, 152 mSolverCounterSat, 53 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 128 SdHoareTripleChecker+Invalid, 206 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 53 IncrementalHoareTripleChecker+Valid, 152 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.2s IncrementalHoareTripleChecker+Time [2024-11-18 13:29:35,347 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 128 Invalid, 206 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [53 Valid, 152 Invalid, 1 Unknown, 0 Unchecked, 4.2s Time] [2024-11-18 13:29:35,348 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2024-11-18 13:29:35,373 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 80. [2024-11-18 13:29:35,373 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 80 states, 42 states have (on average 1.0714285714285714) internal successors, (45), 45 states have internal predecessors, (45), 27 states have call successors, (27), 10 states have call predecessors, (27), 10 states have return successors, (26), 24 states have call predecessors, (26), 26 states have call successors, (26) [2024-11-18 13:29:35,374 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 80 states to 80 states and 98 transitions. [2024-11-18 13:29:35,375 INFO L78 Accepts]: Start accepts. Automaton has 80 states and 98 transitions. Word has length 46 [2024-11-18 13:29:35,375 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:29:35,375 INFO L471 AbstractCegarLoop]: Abstraction has 80 states and 98 transitions. [2024-11-18 13:29:35,376 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 1.8461538461538463) internal successors, (24), 11 states have internal predecessors, (24), 5 states have call successors, (16), 3 states have call predecessors, (16), 2 states have return successors, (14), 4 states have call predecessors, (14), 5 states have call successors, (14) [2024-11-18 13:29:35,376 INFO L276 IsEmpty]: Start isEmpty. Operand 80 states and 98 transitions. [2024-11-18 13:29:35,377 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2024-11-18 13:29:35,377 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:29:35,377 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:29:35,394 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-18 13:29:35,581 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-18 13:29:35,582 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:29:35,582 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:29:35,582 INFO L85 PathProgramCache]: Analyzing trace with hash 900098756, now seen corresponding path program 3 times [2024-11-18 13:29:35,582 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:29:35,582 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [194545398] [2024-11-18 13:29:35,583 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-18 13:29:35,583 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:29:35,617 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2024-11-18 13:29:35,617 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:29:35,618 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1415668906] [2024-11-18 13:29:35,618 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-18 13:29:35,618 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:29:35,618 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:29:35,625 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-18 13:29:35,626 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-18 13:29:35,675 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2024-11-18 13:29:35,675 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:29:35,676 INFO L255 TraceCheckSpWp]: Trace formula consists of 74 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-11-18 13:29:35,678 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:29:35,792 INFO L134 CoverageAnalysis]: Checked inductivity of 133 backedges. 16 proven. 5 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2024-11-18 13:29:35,794 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:29:35,965 INFO L134 CoverageAnalysis]: Checked inductivity of 133 backedges. 16 proven. 5 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2024-11-18 13:29:35,966 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:29:35,966 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [194545398] [2024-11-18 13:29:35,966 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:29:35,966 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1415668906] [2024-11-18 13:29:35,966 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1415668906] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:29:35,966 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:29:35,966 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2024-11-18 13:29:35,966 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1026131732] [2024-11-18 13:29:35,966 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:29:35,967 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-18 13:29:35,967 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:29:35,969 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-18 13:29:35,969 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=67, Unknown=0, NotChecked=0, Total=90 [2024-11-18 13:29:35,969 INFO L87 Difference]: Start difference. First operand 80 states and 98 transitions. Second operand has 10 states, 10 states have (on average 1.9) internal successors, (19), 8 states have internal predecessors, (19), 4 states have call successors, (18), 3 states have call predecessors, (18), 1 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) [2024-11-18 13:29:36,180 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:29:36,180 INFO L93 Difference]: Finished difference Result 96 states and 112 transitions. [2024-11-18 13:29:36,181 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-18 13:29:36,181 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 1.9) internal successors, (19), 8 states have internal predecessors, (19), 4 states have call successors, (18), 3 states have call predecessors, (18), 1 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) Word has length 51 [2024-11-18 13:29:36,181 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:29:36,182 INFO L225 Difference]: With dead ends: 96 [2024-11-18 13:29:36,182 INFO L226 Difference]: Without dead ends: 84 [2024-11-18 13:29:36,183 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 102 GetRequests, 92 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=35, Invalid=97, Unknown=0, NotChecked=0, Total=132 [2024-11-18 13:29:36,183 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 7 mSDsluCounter, 162 mSDsCounter, 0 mSdLazyCounter, 100 mSolverCounterSat, 32 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 200 SdHoareTripleChecker+Invalid, 132 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 32 IncrementalHoareTripleChecker+Valid, 100 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:29:36,183 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 200 Invalid, 132 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [32 Valid, 100 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:29:36,184 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 84 states. [2024-11-18 13:29:36,202 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 84 to 67. [2024-11-18 13:29:36,221 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 67 states, 42 states have (on average 1.0476190476190477) internal successors, (44), 43 states have internal predecessors, (44), 13 states have call successors, (13), 11 states have call predecessors, (13), 11 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-18 13:29:36,222 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 69 transitions. [2024-11-18 13:29:36,223 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 69 transitions. Word has length 51 [2024-11-18 13:29:36,223 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:29:36,224 INFO L471 AbstractCegarLoop]: Abstraction has 67 states and 69 transitions. [2024-11-18 13:29:36,224 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 1.9) internal successors, (19), 8 states have internal predecessors, (19), 4 states have call successors, (18), 3 states have call predecessors, (18), 1 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) [2024-11-18 13:29:36,225 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 69 transitions. [2024-11-18 13:29:36,226 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2024-11-18 13:29:36,226 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:29:36,226 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:29:36,246 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-18 13:29:36,430 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-18 13:29:36,431 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:29:36,431 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:29:36,431 INFO L85 PathProgramCache]: Analyzing trace with hash 1061977627, now seen corresponding path program 1 times [2024-11-18 13:29:36,431 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:29:36,432 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [988722184] [2024-11-18 13:29:36,432 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:29:36,432 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:29:36,461 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:29:36,467 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [646110035] [2024-11-18 13:29:36,467 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:29:36,467 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:29:36,468 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:29:36,469 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-18 13:29:36,471 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-18 13:29:36,531 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:29:36,532 INFO L255 TraceCheckSpWp]: Trace formula consists of 156 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-11-18 13:29:36,536 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:29:36,692 INFO L134 CoverageAnalysis]: Checked inductivity of 249 backedges. 22 proven. 7 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2024-11-18 13:29:36,692 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:29:37,112 INFO L134 CoverageAnalysis]: Checked inductivity of 249 backedges. 22 proven. 7 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2024-11-18 13:29:37,112 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:29:37,113 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [988722184] [2024-11-18 13:29:37,113 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:29:37,113 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [646110035] [2024-11-18 13:29:37,113 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [646110035] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:29:37,113 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:29:37,113 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2024-11-18 13:29:37,113 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [301907196] [2024-11-18 13:29:37,114 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:29:37,115 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-18 13:29:37,116 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:29:37,116 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-18 13:29:37,116 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2024-11-18 13:29:37,117 INFO L87 Difference]: Start difference. First operand 67 states and 69 transitions. Second operand has 10 states, 8 states have (on average 2.375) internal successors, (19), 9 states have internal predecessors, (19), 6 states have call successors, (24), 2 states have call predecessors, (24), 1 states have return successors, (22), 6 states have call predecessors, (22), 6 states have call successors, (22) [2024-11-18 13:29:37,491 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:29:37,491 INFO L93 Difference]: Finished difference Result 97 states and 113 transitions. [2024-11-18 13:29:37,492 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-18 13:29:37,492 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 2.375) internal successors, (19), 9 states have internal predecessors, (19), 6 states have call successors, (24), 2 states have call predecessors, (24), 1 states have return successors, (22), 6 states have call predecessors, (22), 6 states have call successors, (22) Word has length 67 [2024-11-18 13:29:37,493 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:29:37,493 INFO L225 Difference]: With dead ends: 97 [2024-11-18 13:29:37,494 INFO L226 Difference]: Without dead ends: 95 [2024-11-18 13:29:37,494 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 135 GetRequests, 122 SyntacticMatches, 2 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=41, Invalid=115, Unknown=0, NotChecked=0, Total=156 [2024-11-18 13:29:37,495 INFO L432 NwaCegarLoop]: 27 mSDtfsCounter, 5 mSDsluCounter, 127 mSDsCounter, 0 mSdLazyCounter, 97 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 154 SdHoareTripleChecker+Invalid, 110 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 97 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-18 13:29:37,495 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 154 Invalid, 110 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 97 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-18 13:29:37,496 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 95 states. [2024-11-18 13:29:37,555 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 95 to 91. [2024-11-18 13:29:37,556 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 91 states, 52 states have (on average 1.0769230769230769) internal successors, (56), 54 states have internal predecessors, (56), 25 states have call successors, (25), 13 states have call predecessors, (25), 13 states have return successors, (24), 23 states have call predecessors, (24), 24 states have call successors, (24) [2024-11-18 13:29:37,556 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 105 transitions. [2024-11-18 13:29:37,557 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 105 transitions. Word has length 67 [2024-11-18 13:29:37,557 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:29:37,557 INFO L471 AbstractCegarLoop]: Abstraction has 91 states and 105 transitions. [2024-11-18 13:29:37,558 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 2.375) internal successors, (19), 9 states have internal predecessors, (19), 6 states have call successors, (24), 2 states have call predecessors, (24), 1 states have return successors, (22), 6 states have call predecessors, (22), 6 states have call successors, (22) [2024-11-18 13:29:37,558 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 105 transitions. [2024-11-18 13:29:37,559 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2024-11-18 13:29:37,559 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:29:37,559 INFO L215 NwaCegarLoop]: trace histogram [13, 12, 12, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:29:37,576 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-18 13:29:37,763 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:29:37,764 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:29:37,764 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:29:37,764 INFO L85 PathProgramCache]: Analyzing trace with hash -1246911088, now seen corresponding path program 1 times [2024-11-18 13:29:37,764 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:29:37,765 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2051742536] [2024-11-18 13:29:37,765 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:29:37,765 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:29:37,804 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:29:37,808 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [686236868] [2024-11-18 13:29:37,808 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:29:37,810 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:29:37,810 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:29:37,812 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-18 13:29:37,815 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-18 13:29:37,872 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:29:37,874 INFO L255 TraceCheckSpWp]: Trace formula consists of 165 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-11-18 13:29:37,877 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:29:38,131 INFO L134 CoverageAnalysis]: Checked inductivity of 295 backedges. 24 proven. 7 refuted. 0 times theorem prover too weak. 264 trivial. 0 not checked. [2024-11-18 13:29:38,131 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:29:38,438 INFO L134 CoverageAnalysis]: Checked inductivity of 295 backedges. 24 proven. 7 refuted. 0 times theorem prover too weak. 264 trivial. 0 not checked. [2024-11-18 13:29:38,438 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:29:38,438 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2051742536] [2024-11-18 13:29:38,439 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:29:38,439 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [686236868] [2024-11-18 13:29:38,439 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [686236868] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:29:38,439 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:29:38,439 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7] total 14 [2024-11-18 13:29:38,439 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1421134297] [2024-11-18 13:29:38,439 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:29:38,440 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-18 13:29:38,440 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:29:38,440 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-18 13:29:38,440 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=37, Invalid=145, Unknown=0, NotChecked=0, Total=182 [2024-11-18 13:29:38,441 INFO L87 Difference]: Start difference. First operand 91 states and 105 transitions. Second operand has 14 states, 12 states have (on average 1.9166666666666667) internal successors, (23), 12 states have internal predecessors, (23), 6 states have call successors, (26), 3 states have call predecessors, (26), 1 states have return successors, (24), 6 states have call predecessors, (24), 6 states have call successors, (24) [2024-11-18 13:29:38,833 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:29:38,834 INFO L93 Difference]: Finished difference Result 109 states and 122 transitions. [2024-11-18 13:29:38,834 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-18 13:29:38,834 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 12 states have (on average 1.9166666666666667) internal successors, (23), 12 states have internal predecessors, (23), 6 states have call successors, (26), 3 states have call predecessors, (26), 1 states have return successors, (24), 6 states have call predecessors, (24), 6 states have call successors, (24) Word has length 72 [2024-11-18 13:29:38,834 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:29:38,836 INFO L225 Difference]: With dead ends: 109 [2024-11-18 13:29:38,839 INFO L226 Difference]: Without dead ends: 89 [2024-11-18 13:29:38,839 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 148 GetRequests, 130 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 49 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=84, Invalid=296, Unknown=0, NotChecked=0, Total=380 [2024-11-18 13:29:38,840 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 15 mSDsluCounter, 197 mSDsCounter, 0 mSdLazyCounter, 151 mSolverCounterSat, 31 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 225 SdHoareTripleChecker+Invalid, 182 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 31 IncrementalHoareTripleChecker+Valid, 151 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-18 13:29:38,840 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [20 Valid, 225 Invalid, 182 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [31 Valid, 151 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-18 13:29:38,841 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states. [2024-11-18 13:29:38,872 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 89. [2024-11-18 13:29:38,874 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 89 states, 52 states have (on average 1.0384615384615385) internal successors, (54), 53 states have internal predecessors, (54), 23 states have call successors, (23), 13 states have call predecessors, (23), 13 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2024-11-18 13:29:38,876 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 99 transitions. [2024-11-18 13:29:38,877 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 99 transitions. Word has length 72 [2024-11-18 13:29:38,877 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:29:38,877 INFO L471 AbstractCegarLoop]: Abstraction has 89 states and 99 transitions. [2024-11-18 13:29:38,877 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 12 states have (on average 1.9166666666666667) internal successors, (23), 12 states have internal predecessors, (23), 6 states have call successors, (26), 3 states have call predecessors, (26), 1 states have return successors, (24), 6 states have call predecessors, (24), 6 states have call successors, (24) [2024-11-18 13:29:38,879 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 99 transitions. [2024-11-18 13:29:38,883 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 122 [2024-11-18 13:29:38,883 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:29:38,883 INFO L215 NwaCegarLoop]: trace histogram [22, 21, 21, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:29:38,900 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-18 13:29:39,083 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,SelfDestructingSolverStorable9 [2024-11-18 13:29:39,084 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:29:39,084 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:29:39,085 INFO L85 PathProgramCache]: Analyzing trace with hash -1837317061, now seen corresponding path program 2 times [2024-11-18 13:29:39,085 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:29:39,085 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1604061608] [2024-11-18 13:29:39,085 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:29:39,085 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:29:39,135 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:29:39,135 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:29:39,137 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1496968502] [2024-11-18 13:29:39,137 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:29:39,137 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:29:39,137 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:29:39,139 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-18 13:29:39,141 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-18 13:29:39,223 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:29:39,223 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:29:39,230 INFO L255 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 40 conjuncts are in the unsatisfiable core [2024-11-18 13:29:39,233 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:29:39,575 INFO L134 CoverageAnalysis]: Checked inductivity of 924 backedges. 86 proven. 58 refuted. 0 times theorem prover too weak. 780 trivial. 0 not checked. [2024-11-18 13:29:39,576 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:29:40,469 INFO L134 CoverageAnalysis]: Checked inductivity of 924 backedges. 107 proven. 16 refuted. 0 times theorem prover too weak. 801 trivial. 0 not checked. [2024-11-18 13:29:40,469 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:29:40,469 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1604061608] [2024-11-18 13:29:40,469 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:29:40,469 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1496968502] [2024-11-18 13:29:40,470 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1496968502] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:29:40,470 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:29:40,470 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 8] total 17 [2024-11-18 13:29:40,470 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [861201335] [2024-11-18 13:29:40,470 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:29:40,471 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-18 13:29:40,471 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:29:40,471 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-18 13:29:40,472 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=49, Invalid=223, Unknown=0, NotChecked=0, Total=272 [2024-11-18 13:29:40,472 INFO L87 Difference]: Start difference. First operand 89 states and 99 transitions. Second operand has 17 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 14 states have internal predecessors, (31), 10 states have call successors, (34), 3 states have call predecessors, (34), 2 states have return successors, (32), 8 states have call predecessors, (32), 9 states have call successors, (32) [2024-11-18 13:29:41,045 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:29:41,045 INFO L93 Difference]: Finished difference Result 111 states and 128 transitions. [2024-11-18 13:29:41,045 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-18 13:29:41,046 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 14 states have internal predecessors, (31), 10 states have call successors, (34), 3 states have call predecessors, (34), 2 states have return successors, (32), 8 states have call predecessors, (32), 9 states have call successors, (32) Word has length 121 [2024-11-18 13:29:41,046 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:29:41,047 INFO L225 Difference]: With dead ends: 111 [2024-11-18 13:29:41,047 INFO L226 Difference]: Without dead ends: 107 [2024-11-18 13:29:41,048 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 244 GetRequests, 225 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 41 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=73, Invalid=347, Unknown=0, NotChecked=0, Total=420 [2024-11-18 13:29:41,048 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 8 mSDsluCounter, 299 mSDsCounter, 0 mSdLazyCounter, 382 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 332 SdHoareTripleChecker+Invalid, 404 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 382 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-18 13:29:41,048 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 332 Invalid, 404 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 382 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-18 13:29:41,049 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 107 states. [2024-11-18 13:29:41,082 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 107 to 103. [2024-11-18 13:29:41,083 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 103 states, 59 states have (on average 1.0338983050847457) internal successors, (61), 60 states have internal predecessors, (61), 29 states have call successors, (29), 15 states have call predecessors, (29), 14 states have return successors, (28), 27 states have call predecessors, (28), 28 states have call successors, (28) [2024-11-18 13:29:41,083 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 103 states to 103 states and 118 transitions. [2024-11-18 13:29:41,084 INFO L78 Accepts]: Start accepts. Automaton has 103 states and 118 transitions. Word has length 121 [2024-11-18 13:29:41,084 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:29:41,084 INFO L471 AbstractCegarLoop]: Abstraction has 103 states and 118 transitions. [2024-11-18 13:29:41,085 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 14 states have internal predecessors, (31), 10 states have call successors, (34), 3 states have call predecessors, (34), 2 states have return successors, (32), 8 states have call predecessors, (32), 9 states have call successors, (32) [2024-11-18 13:29:41,085 INFO L276 IsEmpty]: Start isEmpty. Operand 103 states and 118 transitions. [2024-11-18 13:29:41,087 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 127 [2024-11-18 13:29:41,087 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:29:41,088 INFO L215 NwaCegarLoop]: trace histogram [23, 22, 22, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:29:41,106 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-11-18 13:29:41,291 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:29:41,292 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:29:41,292 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:29:41,292 INFO L85 PathProgramCache]: Analyzing trace with hash -1974193296, now seen corresponding path program 2 times [2024-11-18 13:29:41,292 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:29:41,292 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [164923224] [2024-11-18 13:29:41,292 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:29:41,293 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:29:41,344 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:29:41,344 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:29:41,346 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [736665365] [2024-11-18 13:29:41,346 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:29:41,346 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:29:41,347 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:29:41,348 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-18 13:29:41,349 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-18 13:29:41,425 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:29:41,426 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:29:41,428 INFO L255 TraceCheckSpWp]: Trace formula consists of 275 conjuncts, 39 conjuncts are in the unsatisfiable core [2024-11-18 13:29:41,431 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:29:41,739 INFO L134 CoverageAnalysis]: Checked inductivity of 1010 backedges. 88 proven. 61 refuted. 0 times theorem prover too weak. 861 trivial. 0 not checked. [2024-11-18 13:29:41,739 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:29:42,414 INFO L134 CoverageAnalysis]: Checked inductivity of 1010 backedges. 88 proven. 40 refuted. 0 times theorem prover too weak. 882 trivial. 0 not checked. [2024-11-18 13:29:42,415 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:29:42,415 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [164923224] [2024-11-18 13:29:42,415 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:29:42,415 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [736665365] [2024-11-18 13:29:42,415 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [736665365] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:29:42,415 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:29:42,415 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 9] total 18 [2024-11-18 13:29:42,415 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1358120472] [2024-11-18 13:29:42,415 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:29:42,416 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2024-11-18 13:29:42,416 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:29:42,417 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2024-11-18 13:29:42,417 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=246, Unknown=0, NotChecked=0, Total=306 [2024-11-18 13:29:42,417 INFO L87 Difference]: Start difference. First operand 103 states and 118 transitions. Second operand has 18 states, 15 states have (on average 2.066666666666667) internal successors, (31), 15 states have internal predecessors, (31), 10 states have call successors, (36), 3 states have call predecessors, (36), 2 states have return successors, (34), 8 states have call predecessors, (34), 10 states have call successors, (34) [2024-11-18 13:29:42,874 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:29:42,874 INFO L93 Difference]: Finished difference Result 119 states and 133 transitions. [2024-11-18 13:29:42,874 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-18 13:29:42,875 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 15 states have (on average 2.066666666666667) internal successors, (31), 15 states have internal predecessors, (31), 10 states have call successors, (36), 3 states have call predecessors, (36), 2 states have return successors, (34), 8 states have call predecessors, (34), 10 states have call successors, (34) Word has length 126 [2024-11-18 13:29:42,875 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:29:42,875 INFO L225 Difference]: With dead ends: 119 [2024-11-18 13:29:42,875 INFO L226 Difference]: Without dead ends: 0 [2024-11-18 13:29:42,878 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 256 GetRequests, 233 SyntacticMatches, 1 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 70 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=113, Invalid=439, Unknown=0, NotChecked=0, Total=552 [2024-11-18 13:29:42,878 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 7 mSDsluCounter, 175 mSDsCounter, 0 mSdLazyCounter, 314 mSolverCounterSat, 20 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 207 SdHoareTripleChecker+Invalid, 334 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 20 IncrementalHoareTripleChecker+Valid, 314 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-18 13:29:42,878 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 207 Invalid, 334 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [20 Valid, 314 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-18 13:29:42,879 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2024-11-18 13:29:42,879 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2024-11-18 13:29:42,880 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-18 13:29:42,880 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2024-11-18 13:29:42,880 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 126 [2024-11-18 13:29:42,880 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:29:42,880 INFO L471 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-18 13:29:42,880 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 15 states have (on average 2.066666666666667) internal successors, (31), 15 states have internal predecessors, (31), 10 states have call successors, (36), 3 states have call predecessors, (36), 2 states have return successors, (34), 8 states have call predecessors, (34), 10 states have call successors, (34) [2024-11-18 13:29:42,880 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2024-11-18 13:29:42,881 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2024-11-18 13:29:42,883 INFO L782 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2024-11-18 13:29:42,901 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-18 13:29:43,087 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,SelfDestructingSolverStorable11 [2024-11-18 13:29:43,090 INFO L407 BasicCegarLoop]: Path program histogram: [3, 2, 2, 1, 1, 1, 1, 1] [2024-11-18 13:29:43,092 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2024-11-18 13:29:47,084 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2024-11-18 13:29:47,111 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 18.11 01:29:47 BoogieIcfgContainer [2024-11-18 13:29:47,111 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-11-18 13:29:47,111 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-18 13:29:47,111 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-18 13:29:47,112 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-18 13:29:47,112 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.11 01:29:26" (3/4) ... [2024-11-18 13:29:47,117 INFO L142 WitnessPrinter]: Generating witness for correct program [2024-11-18 13:29:47,120 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure __VERIFIER_assert [2024-11-18 13:29:47,124 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 12 nodes and edges [2024-11-18 13:29:47,124 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 4 nodes and edges [2024-11-18 13:29:47,124 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 3 nodes and edges [2024-11-18 13:29:47,124 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2024-11-18 13:29:47,210 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.graphml [2024-11-18 13:29:47,211 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.yml [2024-11-18 13:29:47,211 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-18 13:29:47,211 INFO L158 Benchmark]: Toolchain (without parser) took 20994.98ms. Allocated memory was 140.5MB in the beginning and 211.8MB in the end (delta: 71.3MB). Free memory was 104.3MB in the beginning and 145.6MB in the end (delta: -41.3MB). Peak memory consumption was 29.3MB. Max. memory is 16.1GB. [2024-11-18 13:29:47,212 INFO L158 Benchmark]: CDTParser took 0.20ms. Allocated memory is still 140.5MB. Free memory is still 109.7MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-18 13:29:47,212 INFO L158 Benchmark]: CACSL2BoogieTranslator took 265.70ms. Allocated memory is still 140.5MB. Free memory was 103.9MB in the beginning and 91.2MB in the end (delta: 12.7MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2024-11-18 13:29:47,212 INFO L158 Benchmark]: Boogie Procedure Inliner took 32.23ms. Allocated memory is still 140.5MB. Free memory was 90.8MB in the beginning and 89.2MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-18 13:29:47,212 INFO L158 Benchmark]: Boogie Preprocessor took 38.27ms. Allocated memory is still 140.5MB. Free memory was 89.2MB in the beginning and 87.5MB in the end (delta: 1.7MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-18 13:29:47,213 INFO L158 Benchmark]: RCFGBuilder took 405.94ms. Allocated memory is still 140.5MB. Free memory was 87.5MB in the beginning and 106.9MB in the end (delta: -19.4MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-11-18 13:29:47,213 INFO L158 Benchmark]: TraceAbstraction took 20146.17ms. Allocated memory was 140.5MB in the beginning and 211.8MB in the end (delta: 71.3MB). Free memory was 106.1MB in the beginning and 149.8MB in the end (delta: -43.7MB). Peak memory consumption was 118.0MB. Max. memory is 16.1GB. [2024-11-18 13:29:47,213 INFO L158 Benchmark]: Witness Printer took 99.57ms. Allocated memory is still 211.8MB. Free memory was 149.8MB in the beginning and 145.6MB in the end (delta: 4.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. [2024-11-18 13:29:47,218 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.20ms. Allocated memory is still 140.5MB. Free memory is still 109.7MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 265.70ms. Allocated memory is still 140.5MB. Free memory was 103.9MB in the beginning and 91.2MB in the end (delta: 12.7MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 32.23ms. Allocated memory is still 140.5MB. Free memory was 90.8MB in the beginning and 89.2MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 38.27ms. Allocated memory is still 140.5MB. Free memory was 89.2MB in the beginning and 87.5MB in the end (delta: 1.7MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 405.94ms. Allocated memory is still 140.5MB. Free memory was 87.5MB in the beginning and 106.9MB in the end (delta: -19.4MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * TraceAbstraction took 20146.17ms. Allocated memory was 140.5MB in the beginning and 211.8MB in the end (delta: 71.3MB). Free memory was 106.1MB in the beginning and 149.8MB in the end (delta: -43.7MB). Peak memory consumption was 118.0MB. Max. memory is 16.1GB. * Witness Printer took 99.57ms. Allocated memory is still 211.8MB. Free memory was 149.8MB in the beginning and 145.6MB in the end (delta: 4.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - PositiveResult [Line: 17]: a call to reach_error is unreachable For all program executions holds that a call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 27 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 16.1s, OverallIterations: 12, TraceHistogramMax: 23, PathProgramHistogramMax: 3, EmptinessCheckTime: 0.0s, AutomataDifference: 7.4s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 1 mSolverCounterUnknown, 130 SdHoareTripleChecker+Valid, 6.2s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 78 mSDsluCounter, 1829 SdHoareTripleChecker+Invalid, 5.9s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 1471 mSDsCounter, 233 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1512 IncrementalHoareTripleChecker+Invalid, 1746 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 233 mSolverCounterUnsat, 358 mSDtfsCounter, 1512 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 1127 GetRequests, 999 SyntacticMatches, 3 SemanticMatches, 125 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 214 ImplicationChecksByTransitivity, 2.1s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=103occurred in iteration=11, InterpolantAutomatonStates: 98, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.3s AutomataMinimizationTime, 12 MinimizatonAttempts, 54 StatesRemovedByMinimization, 7 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.6s SatisfiabilityAnalysisTime, 4.9s InterpolantComputationTime, 1180 NumberOfCodeBlocks, 1150 NumberOfCodeBlocksAsserted, 34 NumberOfCheckSat, 1104 ConstructedInterpolants, 0 QuantifiedInterpolants, 4759 SizeOfPredicates, 19 NumberOfNonLiveVariables, 1357 ConjunctsInSsa, 210 ConjunctsInUnsatCore, 19 InterpolantComputations, 5 PerfectInterpolantSequences, 5309/5604 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold - InvariantResult [Line: 33]: Loop Invariant Derived loop invariant: ((((((a <= 100) && ((((__int128) y * z) + ((__int128) 2 * z)) == ((6 + ((__int128) y * 12)) + ((__int128) x * 18)))) && ((((__int128) x * z) == (((__int128) x * 12) + (6 * ((__int128) a * x)))) || (n < (a + 1)))) && (((((__int128) y * z) + 6) + ((__int128) z * z)) == ((((__int128) z * 4) + ((__int128) x * 18)) + ((__int128) y * 24)))) && (z == (6 + ((__int128) 6 * n)))) && (0 <= a)) - ProcedureContractResult [Line: 14]: Procedure Contract for __VERIFIER_assert Derived contract for procedure __VERIFIER_assert. Requires: (cond != 0) Ensures: (cond != 0) RESULT: Ultimate proved your program to be correct! [2024-11-18 13:29:47,238 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE