./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound50.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 803cd42f Calling Ultimate with: /root/.sdkman/candidates/java/current/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound50.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 05dbf98a57cbdf117305bcdd9c3dde8d1b2284b890adec5d1f5924f0e5e4bbbb --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.dk.eval-assert-order-craig-803cd42-m [2024-11-22 01:21:58,881 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-22 01:21:58,936 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-22 01:21:58,941 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-22 01:21:58,941 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-22 01:21:58,964 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-22 01:21:58,965 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-22 01:21:58,966 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-22 01:21:58,966 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-22 01:21:58,967 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-22 01:21:58,968 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-22 01:21:58,968 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-22 01:21:58,968 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-22 01:21:58,971 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-22 01:21:58,971 INFO L153 SettingsManager]: * Use SBE=true [2024-11-22 01:21:58,971 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-22 01:21:58,971 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-22 01:21:58,971 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-22 01:21:58,972 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-22 01:21:58,972 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-22 01:21:58,972 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-22 01:21:58,974 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-22 01:21:58,974 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-22 01:21:58,974 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-22 01:21:58,974 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-22 01:21:58,974 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-22 01:21:58,975 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-22 01:21:58,975 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-22 01:21:58,975 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-22 01:21:58,975 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-22 01:21:58,975 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-22 01:21:58,976 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-22 01:21:58,976 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-22 01:21:58,976 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-22 01:21:58,977 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-22 01:21:58,977 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-22 01:21:58,977 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-22 01:21:58,977 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-22 01:21:58,978 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-22 01:21:58,978 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-22 01:21:58,978 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-22 01:21:58,978 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-22 01:21:58,978 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 -> 05dbf98a57cbdf117305bcdd9c3dde8d1b2284b890adec5d1f5924f0e5e4bbbb [2024-11-22 01:21:59,183 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-22 01:21:59,213 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-22 01:21:59,214 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-22 01:21:59,218 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-22 01:21:59,219 INFO L274 PluginConnector]: CDTParser initialized [2024-11-22 01:21:59,219 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound50.c [2024-11-22 01:22:00,491 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-22 01:22:00,667 INFO L384 CDTParser]: Found 1 translation units. [2024-11-22 01:22:00,668 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound50.c [2024-11-22 01:22:00,680 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3680d6b3d/dc3b7d5022284aa8a8ed73a741f842c2/FLAG0b7c049c3 [2024-11-22 01:22:01,061 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3680d6b3d/dc3b7d5022284aa8a8ed73a741f842c2 [2024-11-22 01:22:01,064 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-22 01:22:01,065 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-22 01:22:01,066 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-22 01:22:01,066 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-22 01:22:01,070 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-22 01:22:01,070 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 22.11 01:22:01" (1/1) ... [2024-11-22 01:22:01,071 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4eb74843 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 01:22:01, skipping insertion in model container [2024-11-22 01:22:01,071 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 22.11 01:22:01" (1/1) ... [2024-11-22 01:22:01,086 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-22 01:22:01,281 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound50.c[490,503] [2024-11-22 01:22:01,306 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-22 01:22:01,314 INFO L200 MainTranslator]: Completed pre-run [2024-11-22 01:22:01,324 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound50.c[490,503] [2024-11-22 01:22:01,332 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-22 01:22:01,346 INFO L204 MainTranslator]: Completed translation [2024-11-22 01:22:01,346 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 01:22:01 WrapperNode [2024-11-22 01:22:01,346 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-22 01:22:01,347 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-22 01:22:01,347 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-22 01:22:01,347 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-22 01:22:01,353 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 01:22:01" (1/1) ... [2024-11-22 01:22:01,358 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 01:22:01" (1/1) ... [2024-11-22 01:22:01,383 INFO L138 Inliner]: procedures = 14, calls = 16, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 83 [2024-11-22 01:22:01,384 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-22 01:22:01,384 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-22 01:22:01,384 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-22 01:22:01,384 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-22 01:22:01,394 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 01:22:01" (1/1) ... [2024-11-22 01:22:01,394 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 01:22:01" (1/1) ... [2024-11-22 01:22:01,396 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 01:22:01" (1/1) ... [2024-11-22 01:22:01,406 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-22 01:22:01,406 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 01:22:01" (1/1) ... [2024-11-22 01:22:01,406 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 01:22:01" (1/1) ... [2024-11-22 01:22:01,410 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 01:22:01" (1/1) ... [2024-11-22 01:22:01,413 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 01:22:01" (1/1) ... [2024-11-22 01:22:01,414 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 01:22:01" (1/1) ... [2024-11-22 01:22:01,415 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 01:22:01" (1/1) ... [2024-11-22 01:22:01,416 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-22 01:22:01,420 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-22 01:22:01,421 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-22 01:22:01,421 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-22 01:22:01,421 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 01:22:01" (1/1) ... [2024-11-22 01:22:01,432 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-22 01:22:01,441 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:22:01,455 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-22 01:22:01,457 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-22 01:22:01,494 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-22 01:22:01,494 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-22 01:22:01,494 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-22 01:22:01,494 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-22 01:22:01,494 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-22 01:22:01,494 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-22 01:22:01,494 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-22 01:22:01,494 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-22 01:22:01,543 INFO L238 CfgBuilder]: Building ICFG [2024-11-22 01:22:01,547 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-22 01:22:01,700 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-11-22 01:22:01,700 INFO L287 CfgBuilder]: Performing block encoding [2024-11-22 01:22:01,710 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-22 01:22:01,710 INFO L316 CfgBuilder]: Removed 3 assume(true) statements. [2024-11-22 01:22:01,710 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.11 01:22:01 BoogieIcfgContainer [2024-11-22 01:22:01,710 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-22 01:22:01,712 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-22 01:22:01,712 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-22 01:22:01,718 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-22 01:22:01,721 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 22.11 01:22:01" (1/3) ... [2024-11-22 01:22:01,722 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5c516bf5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.11 01:22:01, skipping insertion in model container [2024-11-22 01:22:01,722 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 01:22:01" (2/3) ... [2024-11-22 01:22:01,722 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5c516bf5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.11 01:22:01, skipping insertion in model container [2024-11-22 01:22:01,722 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.11 01:22:01" (3/3) ... [2024-11-22 01:22:01,723 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd3-ll_valuebound50.c [2024-11-22 01:22:01,735 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-22 01:22:01,736 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-22 01:22:01,776 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-22 01:22:01,781 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;@3eb779a1, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-22 01:22:01,781 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-22 01:22:01,785 INFO L276 IsEmpty]: Start isEmpty. Operand has 35 states, 22 states have (on average 1.5454545454545454) internal successors, (34), 23 states have internal predecessors, (34), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-22 01:22:01,790 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-11-22 01:22:01,790 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:22:01,791 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:22:01,791 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:22:01,795 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:22:01,795 INFO L85 PathProgramCache]: Analyzing trace with hash 872320404, now seen corresponding path program 1 times [2024-11-22 01:22:01,802 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:22:01,802 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [553283787] [2024-11-22 01:22:01,802 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:22:01,803 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:22:01,884 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:22:01,928 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2024-11-22 01:22:01,929 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:22:01,929 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [553283787] [2024-11-22 01:22:01,930 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [553283787] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-22 01:22:01,930 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [319490257] [2024-11-22 01:22:01,930 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:22:01,930 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:22:01,930 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:22:01,932 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-22 01:22:01,934 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-22 01:22:01,979 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:22:01,980 INFO L255 TraceCheckSpWp]: Trace formula consists of 83 conjuncts, 1 conjuncts are in the unsatisfiable core [2024-11-22 01:22:01,983 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:22:01,992 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2024-11-22 01:22:01,992 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-22 01:22:01,992 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [319490257] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-22 01:22:01,992 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-22 01:22:01,993 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2024-11-22 01:22:01,994 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1556429937] [2024-11-22 01:22:01,995 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-22 01:22:01,997 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-22 01:22:01,998 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:22:02,012 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-22 01:22:02,012 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-22 01:22:02,014 INFO L87 Difference]: Start difference. First operand has 35 states, 22 states have (on average 1.5454545454545454) internal successors, (34), 23 states have internal predecessors, (34), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand has 2 states, 2 states have (on average 6.5) internal successors, (13), 2 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-22 01:22:02,028 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:22:02,028 INFO L93 Difference]: Finished difference Result 67 states and 109 transitions. [2024-11-22 01:22:02,029 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-22 01:22:02,030 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 6.5) internal successors, (13), 2 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) Word has length 29 [2024-11-22 01:22:02,030 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:22:02,035 INFO L225 Difference]: With dead ends: 67 [2024-11-22 01:22:02,035 INFO L226 Difference]: Without dead ends: 31 [2024-11-22 01:22:02,037 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 30 GetRequests, 30 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-22 01:22:02,039 INFO L432 NwaCegarLoop]: 44 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 44 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-22 01:22:02,040 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 44 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-22 01:22:02,054 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2024-11-22 01:22:02,069 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 31. [2024-11-22 01:22:02,070 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31 states, 19 states have (on average 1.2105263157894737) internal successors, (23), 20 states have internal predecessors, (23), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-22 01:22:02,072 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 40 transitions. [2024-11-22 01:22:02,074 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 40 transitions. Word has length 29 [2024-11-22 01:22:02,074 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:22:02,074 INFO L471 AbstractCegarLoop]: Abstraction has 31 states and 40 transitions. [2024-11-22 01:22:02,075 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 6.5) internal successors, (13), 2 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-22 01:22:02,075 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 40 transitions. [2024-11-22 01:22:02,076 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2024-11-22 01:22:02,076 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:22:02,076 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:22:02,084 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-22 01:22:02,280 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2024-11-22 01:22:02,281 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:22:02,281 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:22:02,281 INFO L85 PathProgramCache]: Analyzing trace with hash 1714405113, now seen corresponding path program 1 times [2024-11-22 01:22:02,282 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:22:02,282 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1849077120] [2024-11-22 01:22:02,282 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:22:02,282 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:22:02,325 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:22:02,529 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 9 proven. 0 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-22 01:22:02,531 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:22:02,532 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1849077120] [2024-11-22 01:22:02,532 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1849077120] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-22 01:22:02,532 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-22 01:22:02,532 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-22 01:22:02,532 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1917223514] [2024-11-22 01:22:02,532 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-22 01:22:02,533 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-22 01:22:02,534 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:22:02,534 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-22 01:22:02,535 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-22 01:22:02,535 INFO L87 Difference]: Start difference. First operand 31 states and 40 transitions. Second operand has 6 states, 6 states have (on average 2.5) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-22 01:22:02,624 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:22:02,624 INFO L93 Difference]: Finished difference Result 50 states and 65 transitions. [2024-11-22 01:22:02,626 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-22 01:22:02,626 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) Word has length 30 [2024-11-22 01:22:02,627 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:22:02,627 INFO L225 Difference]: With dead ends: 50 [2024-11-22 01:22:02,627 INFO L226 Difference]: Without dead ends: 43 [2024-11-22 01:22:02,628 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-22 01:22:02,629 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 20 mSDsluCounter, 89 mSDsCounter, 0 mSdLazyCounter, 60 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 119 SdHoareTripleChecker+Invalid, 60 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 60 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-22 01:22:02,629 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 119 Invalid, 60 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 60 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-22 01:22:02,629 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2024-11-22 01:22:02,638 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 33. [2024-11-22 01:22:02,638 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 21 states have (on average 1.1904761904761905) internal successors, (25), 22 states have internal predecessors, (25), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-22 01:22:02,640 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 42 transitions. [2024-11-22 01:22:02,641 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 42 transitions. Word has length 30 [2024-11-22 01:22:02,641 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:22:02,641 INFO L471 AbstractCegarLoop]: Abstraction has 33 states and 42 transitions. [2024-11-22 01:22:02,641 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-22 01:22:02,641 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 42 transitions. [2024-11-22 01:22:02,642 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2024-11-22 01:22:02,643 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:22:02,643 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:22:02,643 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-22 01:22:02,643 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:22:02,644 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:22:02,644 INFO L85 PathProgramCache]: Analyzing trace with hash -1825736765, now seen corresponding path program 1 times [2024-11-22 01:22:02,645 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:22:02,645 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1251235214] [2024-11-22 01:22:02,645 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:22:02,645 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:22:02,662 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-22 01:22:02,664 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1221443341] [2024-11-22 01:22:02,664 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:22:02,664 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:22:02,664 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:22:02,668 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-22 01:22:02,678 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-22 01:22:02,724 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:22:02,726 INFO L255 TraceCheckSpWp]: Trace formula consists of 95 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-22 01:22:02,728 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:22:02,844 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-22 01:22:02,845 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-22 01:22:02,845 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:22:02,846 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1251235214] [2024-11-22 01:22:02,847 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-22 01:22:02,848 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1221443341] [2024-11-22 01:22:02,848 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1221443341] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-22 01:22:02,848 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-22 01:22:02,848 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-22 01:22:02,848 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [587879468] [2024-11-22 01:22:02,848 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-22 01:22:02,848 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-22 01:22:02,848 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:22:02,849 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-22 01:22:02,849 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-22 01:22:02,851 INFO L87 Difference]: Start difference. First operand 33 states and 42 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-22 01:22:02,891 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:22:02,891 INFO L93 Difference]: Finished difference Result 49 states and 63 transitions. [2024-11-22 01:22:02,892 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-22 01:22:02,892 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 33 [2024-11-22 01:22:02,892 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:22:02,894 INFO L225 Difference]: With dead ends: 49 [2024-11-22 01:22:02,894 INFO L226 Difference]: Without dead ends: 47 [2024-11-22 01:22:02,894 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 33 GetRequests, 29 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-22 01:22:02,895 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 7 mSDsluCounter, 99 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 134 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-22 01:22:02,896 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 134 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-22 01:22:02,897 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2024-11-22 01:22:02,903 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 46. [2024-11-22 01:22:02,904 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 29 states have (on average 1.206896551724138) internal successors, (35), 30 states have internal predecessors, (35), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-22 01:22:02,904 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 60 transitions. [2024-11-22 01:22:02,905 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 60 transitions. Word has length 33 [2024-11-22 01:22:02,905 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:22:02,905 INFO L471 AbstractCegarLoop]: Abstraction has 46 states and 60 transitions. [2024-11-22 01:22:02,905 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-22 01:22:02,905 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 60 transitions. [2024-11-22 01:22:02,906 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2024-11-22 01:22:02,906 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:22:02,906 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:22:02,914 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-22 01:22:03,107 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2024-11-22 01:22:03,108 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:22:03,109 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:22:03,109 INFO L85 PathProgramCache]: Analyzing trace with hash -1547103247, now seen corresponding path program 1 times [2024-11-22 01:22:03,109 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:22:03,109 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1161840689] [2024-11-22 01:22:03,109 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:22:03,109 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:22:03,130 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:22:03,264 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 6 proven. 5 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-22 01:22:03,264 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:22:03,264 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1161840689] [2024-11-22 01:22:03,264 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1161840689] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-22 01:22:03,264 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [993569330] [2024-11-22 01:22:03,264 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:22:03,265 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:22:03,265 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:22:03,268 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-22 01:22:03,269 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-22 01:22:03,307 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:22:03,308 INFO L255 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-22 01:22:03,309 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:22:03,358 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 6 proven. 5 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-22 01:22:03,358 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-22 01:22:03,465 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 6 proven. 5 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-22 01:22:03,466 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [993569330] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-22 01:22:03,466 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-22 01:22:03,466 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 12 [2024-11-22 01:22:03,466 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1528737186] [2024-11-22 01:22:03,466 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-22 01:22:03,467 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-22 01:22:03,467 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:22:03,467 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-22 01:22:03,467 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=103, Unknown=0, NotChecked=0, Total=132 [2024-11-22 01:22:03,468 INFO L87 Difference]: Start difference. First operand 46 states and 60 transitions. Second operand has 12 states, 12 states have (on average 2.5) internal successors, (30), 11 states have internal predecessors, (30), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-22 01:22:03,633 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:22:03,633 INFO L93 Difference]: Finished difference Result 99 states and 139 transitions. [2024-11-22 01:22:03,633 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-22 01:22:03,634 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.5) internal successors, (30), 11 states have internal predecessors, (30), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 35 [2024-11-22 01:22:03,634 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:22:03,635 INFO L225 Difference]: With dead ends: 99 [2024-11-22 01:22:03,635 INFO L226 Difference]: Without dead ends: 92 [2024-11-22 01:22:03,635 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 79 GetRequests, 62 SyntacticMatches, 4 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 38 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=54, Invalid=156, Unknown=0, NotChecked=0, Total=210 [2024-11-22 01:22:03,636 INFO L432 NwaCegarLoop]: 40 mSDtfsCounter, 60 mSDsluCounter, 234 mSDsCounter, 0 mSdLazyCounter, 141 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 68 SdHoareTripleChecker+Valid, 274 SdHoareTripleChecker+Invalid, 163 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 141 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-22 01:22:03,636 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [68 Valid, 274 Invalid, 163 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 141 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-22 01:22:03,637 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2024-11-22 01:22:03,647 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 67. [2024-11-22 01:22:03,648 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 67 states, 46 states have (on average 1.2608695652173914) internal successors, (58), 47 states have internal predecessors, (58), 17 states have call successors, (17), 3 states have call predecessors, (17), 3 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2024-11-22 01:22:03,649 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 91 transitions. [2024-11-22 01:22:03,649 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 91 transitions. Word has length 35 [2024-11-22 01:22:03,649 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:22:03,649 INFO L471 AbstractCegarLoop]: Abstraction has 67 states and 91 transitions. [2024-11-22 01:22:03,649 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 2.5) internal successors, (30), 11 states have internal predecessors, (30), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-22 01:22:03,649 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 91 transitions. [2024-11-22 01:22:03,650 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2024-11-22 01:22:03,650 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:22:03,650 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:22:03,656 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-22 01:22:03,854 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:22:03,855 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:22:03,855 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:22:03,855 INFO L85 PathProgramCache]: Analyzing trace with hash -720434099, now seen corresponding path program 1 times [2024-11-22 01:22:03,855 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:22:03,855 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1399006870] [2024-11-22 01:22:03,855 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:22:03,855 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:22:03,881 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-22 01:22:03,882 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [832143889] [2024-11-22 01:22:03,882 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:22:03,883 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:22:03,883 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:22:03,884 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-22 01:22:03,888 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-22 01:22:03,936 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:22:03,937 INFO L255 TraceCheckSpWp]: Trace formula consists of 104 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-22 01:22:03,939 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:22:04,042 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-22 01:22:04,043 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-22 01:22:04,043 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:22:04,043 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1399006870] [2024-11-22 01:22:04,043 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-22 01:22:04,043 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [832143889] [2024-11-22 01:22:04,043 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [832143889] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-22 01:22:04,043 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-22 01:22:04,044 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-22 01:22:04,044 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1463911562] [2024-11-22 01:22:04,044 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-22 01:22:04,044 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-22 01:22:04,044 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:22:04,045 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-22 01:22:04,048 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-22 01:22:04,048 INFO L87 Difference]: Start difference. First operand 67 states and 91 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-22 01:22:04,115 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:22:04,118 INFO L93 Difference]: Finished difference Result 75 states and 98 transitions. [2024-11-22 01:22:04,118 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-22 01:22:04,121 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 38 [2024-11-22 01:22:04,122 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:22:04,122 INFO L225 Difference]: With dead ends: 75 [2024-11-22 01:22:04,122 INFO L226 Difference]: Without dead ends: 73 [2024-11-22 01:22:04,123 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 38 GetRequests, 34 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-22 01:22:04,123 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 7 mSDsluCounter, 95 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 131 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-22 01:22:04,123 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 131 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-22 01:22:04,125 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2024-11-22 01:22:04,141 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 71. [2024-11-22 01:22:04,142 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 49 states have (on average 1.2448979591836735) internal successors, (61), 50 states have internal predecessors, (61), 17 states have call successors, (17), 4 states have call predecessors, (17), 4 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2024-11-22 01:22:04,143 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 94 transitions. [2024-11-22 01:22:04,144 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 94 transitions. Word has length 38 [2024-11-22 01:22:04,144 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:22:04,144 INFO L471 AbstractCegarLoop]: Abstraction has 71 states and 94 transitions. [2024-11-22 01:22:04,144 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-22 01:22:04,144 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 94 transitions. [2024-11-22 01:22:04,145 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2024-11-22 01:22:04,145 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:22:04,145 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:22:04,155 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-11-22 01:22:04,345 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:22:04,346 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:22:04,346 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:22:04,346 INFO L85 PathProgramCache]: Analyzing trace with hash -376152117, now seen corresponding path program 1 times [2024-11-22 01:22:04,346 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:22:04,346 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1657623472] [2024-11-22 01:22:04,346 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:22:04,346 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:22:04,360 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-22 01:22:04,361 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [315930286] [2024-11-22 01:22:04,361 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:22:04,361 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:22:04,361 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:22:04,363 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-22 01:22:04,364 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-22 01:22:04,410 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:22:04,410 INFO L255 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-11-22 01:22:04,412 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:22:04,492 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-22 01:22:04,492 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-22 01:22:04,555 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-22 01:22:04,555 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:22:04,555 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1657623472] [2024-11-22 01:22:04,555 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-22 01:22:04,555 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [315930286] [2024-11-22 01:22:04,555 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [315930286] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-22 01:22:04,555 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-22 01:22:04,555 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 6] total 9 [2024-11-22 01:22:04,555 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [475863931] [2024-11-22 01:22:04,555 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-22 01:22:04,556 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-22 01:22:04,556 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:22:04,556 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-22 01:22:04,556 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2024-11-22 01:22:04,556 INFO L87 Difference]: Start difference. First operand 71 states and 94 transitions. Second operand has 9 states, 9 states have (on average 3.4444444444444446) internal successors, (31), 8 states have internal predecessors, (31), 3 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-22 01:22:04,662 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:22:04,662 INFO L93 Difference]: Finished difference Result 107 states and 143 transitions. [2024-11-22 01:22:04,662 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-22 01:22:04,663 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 3.4444444444444446) internal successors, (31), 8 states have internal predecessors, (31), 3 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 38 [2024-11-22 01:22:04,663 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:22:04,663 INFO L225 Difference]: With dead ends: 107 [2024-11-22 01:22:04,663 INFO L226 Difference]: Without dead ends: 105 [2024-11-22 01:22:04,664 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 65 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=29, Invalid=81, Unknown=0, NotChecked=0, Total=110 [2024-11-22 01:22:04,664 INFO L432 NwaCegarLoop]: 47 mSDtfsCounter, 30 mSDsluCounter, 158 mSDsCounter, 0 mSdLazyCounter, 68 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 205 SdHoareTripleChecker+Invalid, 86 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 68 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-22 01:22:04,664 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 205 Invalid, 86 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 68 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-22 01:22:04,667 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 105 states. [2024-11-22 01:22:04,686 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 105 to 101. [2024-11-22 01:22:04,688 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 101 states, 70 states have (on average 1.2571428571428571) internal successors, (88), 71 states have internal predecessors, (88), 25 states have call successors, (25), 5 states have call predecessors, (25), 5 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) [2024-11-22 01:22:04,689 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 101 states to 101 states and 137 transitions. [2024-11-22 01:22:04,691 INFO L78 Accepts]: Start accepts. Automaton has 101 states and 137 transitions. Word has length 38 [2024-11-22 01:22:04,692 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:22:04,692 INFO L471 AbstractCegarLoop]: Abstraction has 101 states and 137 transitions. [2024-11-22 01:22:04,692 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 3.4444444444444446) internal successors, (31), 8 states have internal predecessors, (31), 3 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-22 01:22:04,692 INFO L276 IsEmpty]: Start isEmpty. Operand 101 states and 137 transitions. [2024-11-22 01:22:04,693 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2024-11-22 01:22:04,693 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:22:04,693 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:22:04,706 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-22 01:22:04,895 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:22:04,895 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:22:04,896 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:22:04,896 INFO L85 PathProgramCache]: Analyzing trace with hash 279172547, now seen corresponding path program 1 times [2024-11-22 01:22:04,896 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:22:04,896 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1110907549] [2024-11-22 01:22:04,896 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:22:04,896 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:22:04,914 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-22 01:22:04,918 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [472667432] [2024-11-22 01:22:04,918 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:22:04,919 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:22:04,919 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:22:04,923 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-22 01:22:04,930 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-22 01:22:04,966 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:22:04,972 INFO L255 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-22 01:22:04,973 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:22:05,012 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-22 01:22:05,013 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-22 01:22:05,013 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:22:05,013 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1110907549] [2024-11-22 01:22:05,013 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-22 01:22:05,013 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [472667432] [2024-11-22 01:22:05,013 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [472667432] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-22 01:22:05,013 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-22 01:22:05,013 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-22 01:22:05,013 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [387850029] [2024-11-22 01:22:05,013 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-22 01:22:05,014 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-22 01:22:05,014 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:22:05,014 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-22 01:22:05,014 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-22 01:22:05,014 INFO L87 Difference]: Start difference. First operand 101 states and 137 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2024-11-22 01:22:05,059 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:22:05,060 INFO L93 Difference]: Finished difference Result 147 states and 209 transitions. [2024-11-22 01:22:05,060 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-22 01:22:05,060 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 43 [2024-11-22 01:22:05,060 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:22:05,061 INFO L225 Difference]: With dead ends: 147 [2024-11-22 01:22:05,061 INFO L226 Difference]: Without dead ends: 145 [2024-11-22 01:22:05,062 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 39 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-22 01:22:05,062 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 6 mSDsluCounter, 90 mSDsCounter, 0 mSdLazyCounter, 43 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 43 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-22 01:22:05,062 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 124 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 43 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-22 01:22:05,063 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 145 states. [2024-11-22 01:22:05,078 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 145 to 139. [2024-11-22 01:22:05,078 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 139 states, 87 states have (on average 1.2873563218390804) internal successors, (112), 88 states have internal predecessors, (112), 45 states have call successors, (45), 6 states have call predecessors, (45), 6 states have return successors, (44), 44 states have call predecessors, (44), 44 states have call successors, (44) [2024-11-22 01:22:05,079 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 139 states to 139 states and 201 transitions. [2024-11-22 01:22:05,079 INFO L78 Accepts]: Start accepts. Automaton has 139 states and 201 transitions. Word has length 43 [2024-11-22 01:22:05,080 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:22:05,080 INFO L471 AbstractCegarLoop]: Abstraction has 139 states and 201 transitions. [2024-11-22 01:22:05,080 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2024-11-22 01:22:05,080 INFO L276 IsEmpty]: Start isEmpty. Operand 139 states and 201 transitions. [2024-11-22 01:22:05,081 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2024-11-22 01:22:05,081 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:22:05,081 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:22:05,087 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-22 01:22:05,285 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:22:05,285 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:22:05,285 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:22:05,285 INFO L85 PathProgramCache]: Analyzing trace with hash -2141198011, now seen corresponding path program 1 times [2024-11-22 01:22:05,285 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:22:05,286 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [678181892] [2024-11-22 01:22:05,286 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:22:05,286 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:22:05,299 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-22 01:22:05,299 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1156640026] [2024-11-22 01:22:05,300 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:22:05,300 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:22:05,300 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:22:05,301 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-22 01:22:05,307 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-22 01:22:05,341 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:22:05,342 INFO L255 TraceCheckSpWp]: Trace formula consists of 124 conjuncts, 21 conjuncts are in the unsatisfiable core [2024-11-22 01:22:05,345 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:22:05,448 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 2 proven. 4 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-22 01:22:05,448 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-22 01:22:05,496 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:22:05,496 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [678181892] [2024-11-22 01:22:05,496 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-22 01:22:05,496 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1156640026] [2024-11-22 01:22:05,496 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1156640026] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-22 01:22:05,496 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-22 01:22:05,496 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2024-11-22 01:22:05,496 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [472550773] [2024-11-22 01:22:05,496 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-22 01:22:05,497 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-22 01:22:05,497 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:22:05,497 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-22 01:22:05,497 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2024-11-22 01:22:05,497 INFO L87 Difference]: Start difference. First operand 139 states and 201 transitions. Second operand has 7 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 6 states have internal predecessors, (23), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-22 01:22:05,614 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:22:05,614 INFO L93 Difference]: Finished difference Result 152 states and 212 transitions. [2024-11-22 01:22:05,615 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-22 01:22:05,615 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 6 states have internal predecessors, (23), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 43 [2024-11-22 01:22:05,615 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:22:05,617 INFO L225 Difference]: With dead ends: 152 [2024-11-22 01:22:05,617 INFO L226 Difference]: Without dead ends: 150 [2024-11-22 01:22:05,617 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 39 SyntacticMatches, 2 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2024-11-22 01:22:05,617 INFO L432 NwaCegarLoop]: 42 mSDtfsCounter, 26 mSDsluCounter, 167 mSDsCounter, 0 mSdLazyCounter, 109 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 209 SdHoareTripleChecker+Invalid, 120 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 109 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-22 01:22:05,618 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [33 Valid, 209 Invalid, 120 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 109 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-22 01:22:05,618 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 150 states. [2024-11-22 01:22:05,644 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 150 to 147. [2024-11-22 01:22:05,645 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 147 states, 93 states have (on average 1.2688172043010753) internal successors, (118), 94 states have internal predecessors, (118), 45 states have call successors, (45), 8 states have call predecessors, (45), 8 states have return successors, (44), 44 states have call predecessors, (44), 44 states have call successors, (44) [2024-11-22 01:22:05,646 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 147 states to 147 states and 207 transitions. [2024-11-22 01:22:05,646 INFO L78 Accepts]: Start accepts. Automaton has 147 states and 207 transitions. Word has length 43 [2024-11-22 01:22:05,646 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:22:05,646 INFO L471 AbstractCegarLoop]: Abstraction has 147 states and 207 transitions. [2024-11-22 01:22:05,646 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 6 states have internal predecessors, (23), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-22 01:22:05,646 INFO L276 IsEmpty]: Start isEmpty. Operand 147 states and 207 transitions. [2024-11-22 01:22:05,648 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2024-11-22 01:22:05,648 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:22:05,648 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:22:05,656 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-22 01:22:05,852 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:22:05,853 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:22:05,853 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:22:05,854 INFO L85 PathProgramCache]: Analyzing trace with hash -1796916029, now seen corresponding path program 2 times [2024-11-22 01:22:05,854 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:22:05,854 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [686036592] [2024-11-22 01:22:05,854 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-22 01:22:05,854 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:22:05,870 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-22 01:22:05,870 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-22 01:22:05,954 INFO L134 CoverageAnalysis]: Checked inductivity of 37 backedges. 9 proven. 4 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-22 01:22:05,954 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:22:05,954 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [686036592] [2024-11-22 01:22:05,954 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [686036592] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-22 01:22:05,954 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1700442095] [2024-11-22 01:22:05,954 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-22 01:22:05,955 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:22:05,955 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:22:05,956 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-22 01:22:05,958 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-22 01:22:05,988 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-22 01:22:05,988 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-22 01:22:05,989 INFO L255 TraceCheckSpWp]: Trace formula consists of 135 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-22 01:22:05,990 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:22:06,013 INFO L134 CoverageAnalysis]: Checked inductivity of 37 backedges. 13 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-22 01:22:06,013 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-22 01:22:06,013 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1700442095] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-22 01:22:06,014 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-22 01:22:06,014 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 9 [2024-11-22 01:22:06,014 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1553772566] [2024-11-22 01:22:06,014 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-22 01:22:06,014 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-22 01:22:06,014 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:22:06,015 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-22 01:22:06,015 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2024-11-22 01:22:06,015 INFO L87 Difference]: Start difference. First operand 147 states and 207 transitions. Second operand has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-22 01:22:06,078 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:22:06,078 INFO L93 Difference]: Finished difference Result 186 states and 259 transitions. [2024-11-22 01:22:06,079 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-22 01:22:06,079 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 43 [2024-11-22 01:22:06,079 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:22:06,080 INFO L225 Difference]: With dead ends: 186 [2024-11-22 01:22:06,080 INFO L226 Difference]: Without dead ends: 130 [2024-11-22 01:22:06,081 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 52 GetRequests, 43 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2024-11-22 01:22:06,081 INFO L432 NwaCegarLoop]: 49 mSDtfsCounter, 18 mSDsluCounter, 111 mSDsCounter, 0 mSdLazyCounter, 54 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 160 SdHoareTripleChecker+Invalid, 62 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 54 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-22 01:22:06,081 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 160 Invalid, 62 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 54 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-22 01:22:06,082 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2024-11-22 01:22:06,104 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 122. [2024-11-22 01:22:06,105 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 122 states, 76 states have (on average 1.2105263157894737) internal successors, (92), 77 states have internal predecessors, (92), 37 states have call successors, (37), 8 states have call predecessors, (37), 8 states have return successors, (36), 36 states have call predecessors, (36), 36 states have call successors, (36) [2024-11-22 01:22:06,106 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 122 states to 122 states and 165 transitions. [2024-11-22 01:22:06,106 INFO L78 Accepts]: Start accepts. Automaton has 122 states and 165 transitions. Word has length 43 [2024-11-22 01:22:06,109 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:22:06,109 INFO L471 AbstractCegarLoop]: Abstraction has 122 states and 165 transitions. [2024-11-22 01:22:06,109 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-22 01:22:06,109 INFO L276 IsEmpty]: Start isEmpty. Operand 122 states and 165 transitions. [2024-11-22 01:22:06,110 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2024-11-22 01:22:06,110 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:22:06,110 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:22:06,121 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-22 01:22:06,311 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2024-11-22 01:22:06,312 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:22:06,312 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:22:06,312 INFO L85 PathProgramCache]: Analyzing trace with hash -1189241395, now seen corresponding path program 1 times [2024-11-22 01:22:06,312 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:22:06,312 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1191105586] [2024-11-22 01:22:06,312 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:22:06,313 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:22:06,329 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-22 01:22:06,331 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2048978189] [2024-11-22 01:22:06,331 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:22:06,331 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:22:06,332 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:22:06,333 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-22 01:22:06,334 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-22 01:22:06,370 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:22:06,370 INFO L255 TraceCheckSpWp]: Trace formula consists of 122 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-22 01:22:06,371 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:22:06,429 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-11-22 01:22:06,429 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-22 01:22:06,430 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:22:06,430 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1191105586] [2024-11-22 01:22:06,430 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-22 01:22:06,430 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2048978189] [2024-11-22 01:22:06,430 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2048978189] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-22 01:22:06,430 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-22 01:22:06,430 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-22 01:22:06,431 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [836393262] [2024-11-22 01:22:06,431 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-22 01:22:06,431 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-22 01:22:06,431 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:22:06,432 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-22 01:22:06,432 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-22 01:22:06,432 INFO L87 Difference]: Start difference. First operand 122 states and 165 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-22 01:22:06,506 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:22:06,506 INFO L93 Difference]: Finished difference Result 180 states and 262 transitions. [2024-11-22 01:22:06,506 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-22 01:22:06,507 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 48 [2024-11-22 01:22:06,507 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:22:06,508 INFO L225 Difference]: With dead ends: 180 [2024-11-22 01:22:06,508 INFO L226 Difference]: Without dead ends: 178 [2024-11-22 01:22:06,509 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 48 GetRequests, 44 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-22 01:22:06,509 INFO L432 NwaCegarLoop]: 37 mSDtfsCounter, 4 mSDsluCounter, 95 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 132 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-22 01:22:06,510 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 132 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-22 01:22:06,510 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 178 states. [2024-11-22 01:22:06,535 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 178 to 166. [2024-11-22 01:22:06,536 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 166 states, 87 states have (on average 1.1839080459770115) internal successors, (103), 96 states have internal predecessors, (103), 69 states have call successors, (69), 9 states have call predecessors, (69), 9 states have return successors, (68), 60 states have call predecessors, (68), 68 states have call successors, (68) [2024-11-22 01:22:06,537 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 166 states to 166 states and 240 transitions. [2024-11-22 01:22:06,538 INFO L78 Accepts]: Start accepts. Automaton has 166 states and 240 transitions. Word has length 48 [2024-11-22 01:22:06,538 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:22:06,538 INFO L471 AbstractCegarLoop]: Abstraction has 166 states and 240 transitions. [2024-11-22 01:22:06,538 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-22 01:22:06,538 INFO L276 IsEmpty]: Start isEmpty. Operand 166 states and 240 transitions. [2024-11-22 01:22:06,539 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2024-11-22 01:22:06,539 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:22:06,539 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:22:06,547 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-22 01:22:06,740 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-11-22 01:22:06,741 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:22:06,741 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:22:06,741 INFO L85 PathProgramCache]: Analyzing trace with hash -828341661, now seen corresponding path program 1 times [2024-11-22 01:22:06,741 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:22:06,741 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1795159887] [2024-11-22 01:22:06,742 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:22:06,742 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:22:06,757 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-22 01:22:06,758 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1247996843] [2024-11-22 01:22:06,759 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:22:06,759 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:22:06,759 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:22:06,761 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-22 01:22:06,762 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-22 01:22:06,807 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:22:06,813 INFO L255 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 51 conjuncts are in the unsatisfiable core [2024-11-22 01:22:06,815 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:22:07,440 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 14 proven. 7 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-22 01:22:07,440 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-22 01:22:07,848 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 8 proven. 4 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-11-22 01:22:07,849 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:22:07,849 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1795159887] [2024-11-22 01:22:07,849 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-22 01:22:07,849 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1247996843] [2024-11-22 01:22:07,849 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1247996843] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-22 01:22:07,849 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-22 01:22:07,849 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 23 [2024-11-22 01:22:07,849 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1492014352] [2024-11-22 01:22:07,850 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-22 01:22:07,850 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-11-22 01:22:07,850 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:22:07,850 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-22 01:22:07,851 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=77, Invalid=429, Unknown=0, NotChecked=0, Total=506 [2024-11-22 01:22:07,851 INFO L87 Difference]: Start difference. First operand 166 states and 240 transitions. Second operand has 23 states, 21 states have (on average 2.0476190476190474) internal successors, (43), 20 states have internal predecessors, (43), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2024-11-22 01:22:09,559 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:22:09,559 INFO L93 Difference]: Finished difference Result 445 states and 665 transitions. [2024-11-22 01:22:09,559 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2024-11-22 01:22:09,560 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 21 states have (on average 2.0476190476190474) internal successors, (43), 20 states have internal predecessors, (43), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) Word has length 60 [2024-11-22 01:22:09,560 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:22:09,565 INFO L225 Difference]: With dead ends: 445 [2024-11-22 01:22:09,565 INFO L226 Difference]: Without dead ends: 342 [2024-11-22 01:22:09,566 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 141 GetRequests, 97 SyntacticMatches, 0 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 429 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=398, Invalid=1672, Unknown=0, NotChecked=0, Total=2070 [2024-11-22 01:22:09,568 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 172 mSDsluCounter, 327 mSDsCounter, 0 mSdLazyCounter, 556 mSolverCounterSat, 131 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 180 SdHoareTripleChecker+Valid, 357 SdHoareTripleChecker+Invalid, 687 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 131 IncrementalHoareTripleChecker+Valid, 556 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2024-11-22 01:22:09,568 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [180 Valid, 357 Invalid, 687 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [131 Valid, 556 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2024-11-22 01:22:09,569 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 342 states. [2024-11-22 01:22:09,648 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 342 to 256. [2024-11-22 01:22:09,649 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 256 states, 150 states have (on average 1.2066666666666668) internal successors, (181), 157 states have internal predecessors, (181), 93 states have call successors, (93), 12 states have call predecessors, (93), 12 states have return successors, (92), 86 states have call predecessors, (92), 92 states have call successors, (92) [2024-11-22 01:22:09,651 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 256 states to 256 states and 366 transitions. [2024-11-22 01:22:09,651 INFO L78 Accepts]: Start accepts. Automaton has 256 states and 366 transitions. Word has length 60 [2024-11-22 01:22:09,652 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:22:09,653 INFO L471 AbstractCegarLoop]: Abstraction has 256 states and 366 transitions. [2024-11-22 01:22:09,653 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 21 states have (on average 2.0476190476190474) internal successors, (43), 20 states have internal predecessors, (43), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2024-11-22 01:22:09,653 INFO L276 IsEmpty]: Start isEmpty. Operand 256 states and 366 transitions. [2024-11-22 01:22:09,654 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2024-11-22 01:22:09,655 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:22:09,655 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:22:09,664 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-22 01:22:09,858 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2024-11-22 01:22:09,859 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:22:09,859 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:22:09,859 INFO L85 PathProgramCache]: Analyzing trace with hash 1607561902, now seen corresponding path program 1 times [2024-11-22 01:22:09,859 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:22:09,860 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1147457986] [2024-11-22 01:22:09,860 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:22:09,860 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:22:09,877 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-22 01:22:09,881 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [141289039] [2024-11-22 01:22:09,882 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:22:09,882 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:22:09,884 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:22:09,885 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-22 01:22:09,893 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-22 01:22:09,931 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:22:09,932 INFO L255 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-11-22 01:22:09,933 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:22:09,987 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 14 proven. 5 refuted. 0 times theorem prover too weak. 108 trivial. 0 not checked. [2024-11-22 01:22:09,987 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-22 01:22:10,053 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 14 proven. 0 refuted. 0 times theorem prover too weak. 113 trivial. 0 not checked. [2024-11-22 01:22:10,054 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:22:10,054 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1147457986] [2024-11-22 01:22:10,055 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-22 01:22:10,055 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [141289039] [2024-11-22 01:22:10,055 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [141289039] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-22 01:22:10,055 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-22 01:22:10,055 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2024-11-22 01:22:10,055 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [82698548] [2024-11-22 01:22:10,055 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-22 01:22:10,056 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-22 01:22:10,056 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:22:10,056 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-22 01:22:10,056 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-22 01:22:10,056 INFO L87 Difference]: Start difference. First operand 256 states and 366 transitions. Second operand has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-11-22 01:22:10,156 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:22:10,156 INFO L93 Difference]: Finished difference Result 262 states and 371 transitions. [2024-11-22 01:22:10,156 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-22 01:22:10,156 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 70 [2024-11-22 01:22:10,157 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:22:10,158 INFO L225 Difference]: With dead ends: 262 [2024-11-22 01:22:10,158 INFO L226 Difference]: Without dead ends: 260 [2024-11-22 01:22:10,158 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 139 GetRequests, 131 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-22 01:22:10,159 INFO L432 NwaCegarLoop]: 37 mSDtfsCounter, 4 mSDsluCounter, 90 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 127 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-22 01:22:10,159 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 127 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-22 01:22:10,159 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 260 states. [2024-11-22 01:22:10,226 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 260 to 260. [2024-11-22 01:22:10,227 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 260 states, 153 states have (on average 1.2026143790849673) internal successors, (184), 160 states have internal predecessors, (184), 93 states have call successors, (93), 13 states have call predecessors, (93), 13 states have return successors, (92), 86 states have call predecessors, (92), 92 states have call successors, (92) [2024-11-22 01:22:10,228 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 260 states to 260 states and 369 transitions. [2024-11-22 01:22:10,229 INFO L78 Accepts]: Start accepts. Automaton has 260 states and 369 transitions. Word has length 70 [2024-11-22 01:22:10,230 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:22:10,230 INFO L471 AbstractCegarLoop]: Abstraction has 260 states and 369 transitions. [2024-11-22 01:22:10,230 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-11-22 01:22:10,230 INFO L276 IsEmpty]: Start isEmpty. Operand 260 states and 369 transitions. [2024-11-22 01:22:10,230 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2024-11-22 01:22:10,230 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:22:10,231 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:22:10,239 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-11-22 01:22:10,434 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2024-11-22 01:22:10,435 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:22:10,435 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:22:10,435 INFO L85 PathProgramCache]: Analyzing trace with hash -1439093215, now seen corresponding path program 1 times [2024-11-22 01:22:10,436 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:22:10,436 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1499134132] [2024-11-22 01:22:10,436 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:22:10,436 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:22:10,453 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-22 01:22:10,454 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1452881232] [2024-11-22 01:22:10,454 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:22:10,455 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:22:10,455 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:22:10,457 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-22 01:22:10,458 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-22 01:22:10,495 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:22:10,496 INFO L255 TraceCheckSpWp]: Trace formula consists of 183 conjuncts, 50 conjuncts are in the unsatisfiable core [2024-11-22 01:22:10,498 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:22:10,919 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 16 proven. 31 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2024-11-22 01:22:10,919 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-22 01:22:11,056 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 25 proven. 9 refuted. 0 times theorem prover too weak. 43 trivial. 0 not checked. [2024-11-22 01:22:11,056 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:22:11,056 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1499134132] [2024-11-22 01:22:11,056 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-22 01:22:11,057 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1452881232] [2024-11-22 01:22:11,057 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1452881232] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-22 01:22:11,057 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-22 01:22:11,057 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 8] total 22 [2024-11-22 01:22:11,057 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [66789550] [2024-11-22 01:22:11,057 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-22 01:22:11,057 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-11-22 01:22:11,057 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:22:11,058 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-22 01:22:11,058 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=395, Unknown=0, NotChecked=0, Total=462 [2024-11-22 01:22:11,058 INFO L87 Difference]: Start difference. First operand 260 states and 369 transitions. Second operand has 22 states, 22 states have (on average 2.772727272727273) internal successors, (61), 19 states have internal predecessors, (61), 6 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2024-11-22 01:22:12,273 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:22:12,273 INFO L93 Difference]: Finished difference Result 322 states and 459 transitions. [2024-11-22 01:22:12,274 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-11-22 01:22:12,274 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 2.772727272727273) internal successors, (61), 19 states have internal predecessors, (61), 6 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) Word has length 68 [2024-11-22 01:22:12,275 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:22:12,276 INFO L225 Difference]: With dead ends: 322 [2024-11-22 01:22:12,276 INFO L226 Difference]: Without dead ends: 320 [2024-11-22 01:22:12,277 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 155 GetRequests, 123 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 193 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=190, Invalid=932, Unknown=0, NotChecked=0, Total=1122 [2024-11-22 01:22:12,277 INFO L432 NwaCegarLoop]: 52 mSDtfsCounter, 115 mSDsluCounter, 489 mSDsCounter, 0 mSdLazyCounter, 633 mSolverCounterSat, 97 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 117 SdHoareTripleChecker+Valid, 541 SdHoareTripleChecker+Invalid, 730 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 97 IncrementalHoareTripleChecker+Valid, 633 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2024-11-22 01:22:12,277 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [117 Valid, 541 Invalid, 730 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [97 Valid, 633 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2024-11-22 01:22:12,278 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 320 states. [2024-11-22 01:22:12,355 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 320 to 268. [2024-11-22 01:22:12,356 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 268 states, 159 states have (on average 1.1949685534591195) internal successors, (190), 166 states have internal predecessors, (190), 93 states have call successors, (93), 15 states have call predecessors, (93), 15 states have return successors, (92), 86 states have call predecessors, (92), 92 states have call successors, (92) [2024-11-22 01:22:12,358 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 268 states to 268 states and 375 transitions. [2024-11-22 01:22:12,358 INFO L78 Accepts]: Start accepts. Automaton has 268 states and 375 transitions. Word has length 68 [2024-11-22 01:22:12,358 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:22:12,359 INFO L471 AbstractCegarLoop]: Abstraction has 268 states and 375 transitions. [2024-11-22 01:22:12,359 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 2.772727272727273) internal successors, (61), 19 states have internal predecessors, (61), 6 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2024-11-22 01:22:12,359 INFO L276 IsEmpty]: Start isEmpty. Operand 268 states and 375 transitions. [2024-11-22 01:22:12,360 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2024-11-22 01:22:12,360 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:22:12,360 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:22:12,368 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2024-11-22 01:22:12,564 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2024-11-22 01:22:12,565 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:22:12,565 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:22:12,565 INFO L85 PathProgramCache]: Analyzing trace with hash 798002477, now seen corresponding path program 2 times [2024-11-22 01:22:12,565 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:22:12,565 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1514518133] [2024-11-22 01:22:12,566 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-22 01:22:12,566 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:22:12,573 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-22 01:22:12,574 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-22 01:22:12,647 INFO L134 CoverageAnalysis]: Checked inductivity of 108 backedges. 20 proven. 0 refuted. 0 times theorem prover too weak. 88 trivial. 0 not checked. [2024-11-22 01:22:12,647 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:22:12,647 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1514518133] [2024-11-22 01:22:12,647 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1514518133] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-22 01:22:12,648 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-22 01:22:12,648 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-22 01:22:12,648 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [626829254] [2024-11-22 01:22:12,648 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-22 01:22:12,648 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-22 01:22:12,648 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:22:12,648 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-22 01:22:12,648 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-11-22 01:22:12,649 INFO L87 Difference]: Start difference. First operand 268 states and 375 transitions. Second operand has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2024-11-22 01:22:12,754 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:22:12,754 INFO L93 Difference]: Finished difference Result 459 states and 645 transitions. [2024-11-22 01:22:12,754 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-22 01:22:12,754 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) Word has length 73 [2024-11-22 01:22:12,754 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:22:12,756 INFO L225 Difference]: With dead ends: 459 [2024-11-22 01:22:12,756 INFO L226 Difference]: Without dead ends: 289 [2024-11-22 01:22:12,757 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-11-22 01:22:12,757 INFO L432 NwaCegarLoop]: 37 mSDtfsCounter, 0 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 43 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 121 SdHoareTripleChecker+Invalid, 44 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 43 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-22 01:22:12,757 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 121 Invalid, 44 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 43 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-22 01:22:12,758 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 289 states. [2024-11-22 01:22:12,821 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 289 to 277. [2024-11-22 01:22:12,822 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 277 states, 168 states have (on average 1.1964285714285714) internal successors, (201), 169 states have internal predecessors, (201), 93 states have call successors, (93), 15 states have call predecessors, (93), 15 states have return successors, (92), 92 states have call predecessors, (92), 92 states have call successors, (92) [2024-11-22 01:22:12,823 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 277 states to 277 states and 386 transitions. [2024-11-22 01:22:12,824 INFO L78 Accepts]: Start accepts. Automaton has 277 states and 386 transitions. Word has length 73 [2024-11-22 01:22:12,824 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:22:12,824 INFO L471 AbstractCegarLoop]: Abstraction has 277 states and 386 transitions. [2024-11-22 01:22:12,824 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2024-11-22 01:22:12,824 INFO L276 IsEmpty]: Start isEmpty. Operand 277 states and 386 transitions. [2024-11-22 01:22:12,824 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2024-11-22 01:22:12,824 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:22:12,825 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:22:12,825 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13 [2024-11-22 01:22:12,825 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:22:12,825 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:22:12,825 INFO L85 PathProgramCache]: Analyzing trace with hash -1622368081, now seen corresponding path program 3 times [2024-11-22 01:22:12,825 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:22:12,825 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1585192514] [2024-11-22 01:22:12,825 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-22 01:22:12,825 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:22:12,845 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2024-11-22 01:22:12,845 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-22 01:22:12,846 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1024526061] [2024-11-22 01:22:12,846 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-22 01:22:12,846 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:22:12,846 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:22:12,849 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-22 01:22:12,850 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-11-22 01:22:12,896 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-22 01:22:12,897 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-22 01:22:12,898 INFO L255 TraceCheckSpWp]: Trace formula consists of 154 conjuncts, 69 conjuncts are in the unsatisfiable core [2024-11-22 01:22:12,900 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:22:13,670 INFO L134 CoverageAnalysis]: Checked inductivity of 96 backedges. 27 proven. 26 refuted. 0 times theorem prover too weak. 43 trivial. 0 not checked. [2024-11-22 01:22:13,670 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-22 01:22:14,839 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:22:14,840 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1585192514] [2024-11-22 01:22:14,840 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-22 01:22:14,840 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1024526061] [2024-11-22 01:22:14,840 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1024526061] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-22 01:22:14,840 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-22 01:22:14,840 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19] total 19 [2024-11-22 01:22:14,840 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [687757529] [2024-11-22 01:22:14,840 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-22 01:22:14,840 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-22 01:22:14,840 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:22:14,841 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-22 01:22:14,841 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=115, Invalid=587, Unknown=0, NotChecked=0, Total=702 [2024-11-22 01:22:14,842 INFO L87 Difference]: Start difference. First operand 277 states and 386 transitions. Second operand has 19 states, 18 states have (on average 2.1666666666666665) internal successors, (39), 16 states have internal predecessors, (39), 5 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) [2024-11-22 01:22:15,487 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:22:15,487 INFO L93 Difference]: Finished difference Result 344 states and 469 transitions. [2024-11-22 01:22:15,488 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-11-22 01:22:15,488 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 18 states have (on average 2.1666666666666665) internal successors, (39), 16 states have internal predecessors, (39), 5 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) Word has length 73 [2024-11-22 01:22:15,488 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:22:15,490 INFO L225 Difference]: With dead ends: 344 [2024-11-22 01:22:15,490 INFO L226 Difference]: Without dead ends: 342 [2024-11-22 01:22:15,490 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 99 GetRequests, 67 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 230 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=189, Invalid=933, Unknown=0, NotChecked=0, Total=1122 [2024-11-22 01:22:15,491 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 67 mSDsluCounter, 368 mSDsCounter, 0 mSdLazyCounter, 526 mSolverCounterSat, 51 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 83 SdHoareTripleChecker+Valid, 406 SdHoareTripleChecker+Invalid, 577 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 51 IncrementalHoareTripleChecker+Valid, 526 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-22 01:22:15,491 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [83 Valid, 406 Invalid, 577 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [51 Valid, 526 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-22 01:22:15,491 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 342 states. [2024-11-22 01:22:15,571 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 342 to 332. [2024-11-22 01:22:15,572 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 332 states, 202 states have (on average 1.188118811881188) internal successors, (240), 203 states have internal predecessors, (240), 109 states have call successors, (109), 20 states have call predecessors, (109), 20 states have return successors, (108), 108 states have call predecessors, (108), 108 states have call successors, (108) [2024-11-22 01:22:15,573 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 332 states to 332 states and 457 transitions. [2024-11-22 01:22:15,573 INFO L78 Accepts]: Start accepts. Automaton has 332 states and 457 transitions. Word has length 73 [2024-11-22 01:22:15,573 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:22:15,573 INFO L471 AbstractCegarLoop]: Abstraction has 332 states and 457 transitions. [2024-11-22 01:22:15,574 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 18 states have (on average 2.1666666666666665) internal successors, (39), 16 states have internal predecessors, (39), 5 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) [2024-11-22 01:22:15,574 INFO L276 IsEmpty]: Start isEmpty. Operand 332 states and 457 transitions. [2024-11-22 01:22:15,575 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2024-11-22 01:22:15,575 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:22:15,575 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:22:15,583 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2024-11-22 01:22:15,778 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2024-11-22 01:22:15,779 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:22:15,779 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:22:15,779 INFO L85 PathProgramCache]: Analyzing trace with hash 160585404, now seen corresponding path program 1 times [2024-11-22 01:22:15,779 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:22:15,779 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [981242241] [2024-11-22 01:22:15,779 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:22:15,779 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:22:15,809 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-22 01:22:15,810 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [190105634] [2024-11-22 01:22:15,810 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:22:15,810 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:22:15,810 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:22:15,813 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-22 01:22:15,815 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2024-11-22 01:22:15,874 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:22:15,879 INFO L255 TraceCheckSpWp]: Trace formula consists of 215 conjuncts, 71 conjuncts are in the unsatisfiable core [2024-11-22 01:22:15,882 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:22:16,797 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 36 proven. 29 refuted. 0 times theorem prover too weak. 106 trivial. 0 not checked. [2024-11-22 01:22:16,797 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-22 01:22:17,713 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 30 proven. 26 refuted. 0 times theorem prover too weak. 115 trivial. 0 not checked. [2024-11-22 01:22:17,713 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:22:17,713 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [981242241] [2024-11-22 01:22:17,714 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-22 01:22:17,714 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [190105634] [2024-11-22 01:22:17,714 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [190105634] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-22 01:22:17,714 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-22 01:22:17,714 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 16] total 34 [2024-11-22 01:22:17,714 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1995667660] [2024-11-22 01:22:17,714 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-22 01:22:17,714 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 34 states [2024-11-22 01:22:17,714 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:22:17,715 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2024-11-22 01:22:17,715 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=151, Invalid=971, Unknown=0, NotChecked=0, Total=1122 [2024-11-22 01:22:17,715 INFO L87 Difference]: Start difference. First operand 332 states and 457 transitions. Second operand has 34 states, 32 states have (on average 1.9375) internal successors, (62), 32 states have internal predecessors, (62), 10 states have call successors, (23), 3 states have call predecessors, (23), 3 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) [2024-11-22 01:22:30,790 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:22:30,791 INFO L93 Difference]: Finished difference Result 588 states and 848 transitions. [2024-11-22 01:22:30,791 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 86 states. [2024-11-22 01:22:30,791 INFO L78 Accepts]: Start accepts. Automaton has has 34 states, 32 states have (on average 1.9375) internal successors, (62), 32 states have internal predecessors, (62), 10 states have call successors, (23), 3 states have call predecessors, (23), 3 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) Word has length 87 [2024-11-22 01:22:30,792 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:22:30,794 INFO L225 Difference]: With dead ends: 588 [2024-11-22 01:22:30,794 INFO L226 Difference]: Without dead ends: 580 [2024-11-22 01:22:30,797 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 248 GetRequests, 140 SyntacticMatches, 0 SemanticMatches, 108 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3539 ImplicationChecksByTransitivity, 10.3s TimeCoverageRelationStatistics Valid=2167, Invalid=9823, Unknown=0, NotChecked=0, Total=11990 [2024-11-22 01:22:30,797 INFO L432 NwaCegarLoop]: 63 mSDtfsCounter, 304 mSDsluCounter, 1096 mSDsCounter, 0 mSdLazyCounter, 1541 mSolverCounterSat, 326 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 304 SdHoareTripleChecker+Valid, 1159 SdHoareTripleChecker+Invalid, 1867 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 326 IncrementalHoareTripleChecker+Valid, 1541 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.1s IncrementalHoareTripleChecker+Time [2024-11-22 01:22:30,798 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [304 Valid, 1159 Invalid, 1867 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [326 Valid, 1541 Invalid, 0 Unknown, 0 Unchecked, 3.1s Time] [2024-11-22 01:22:30,799 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 580 states. [2024-11-22 01:22:31,047 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 580 to 449. [2024-11-22 01:22:31,048 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 449 states, 269 states have (on average 1.2193308550185873) internal successors, (328), 270 states have internal predecessors, (328), 157 states have call successors, (157), 22 states have call predecessors, (157), 22 states have return successors, (156), 156 states have call predecessors, (156), 156 states have call successors, (156) [2024-11-22 01:22:31,050 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 449 states to 449 states and 641 transitions. [2024-11-22 01:22:31,051 INFO L78 Accepts]: Start accepts. Automaton has 449 states and 641 transitions. Word has length 87 [2024-11-22 01:22:31,051 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:22:31,051 INFO L471 AbstractCegarLoop]: Abstraction has 449 states and 641 transitions. [2024-11-22 01:22:31,051 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 34 states, 32 states have (on average 1.9375) internal successors, (62), 32 states have internal predecessors, (62), 10 states have call successors, (23), 3 states have call predecessors, (23), 3 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) [2024-11-22 01:22:31,051 INFO L276 IsEmpty]: Start isEmpty. Operand 449 states and 641 transitions. [2024-11-22 01:22:31,052 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2024-11-22 01:22:31,052 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:22:31,052 INFO L215 NwaCegarLoop]: trace histogram [11, 10, 10, 4, 4, 4, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:22:31,060 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2024-11-22 01:22:31,256 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:22:31,257 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:22:31,257 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:22:31,257 INFO L85 PathProgramCache]: Analyzing trace with hash -275231594, now seen corresponding path program 1 times [2024-11-22 01:22:31,257 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:22:31,257 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1255045792] [2024-11-22 01:22:31,257 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:22:31,257 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:22:31,271 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-22 01:22:31,272 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [157490353] [2024-11-22 01:22:31,272 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:22:31,272 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:22:31,272 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:22:31,274 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-22 01:22:31,275 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2024-11-22 01:22:31,315 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:22:31,316 INFO L255 TraceCheckSpWp]: Trace formula consists of 203 conjuncts, 32 conjuncts are in the unsatisfiable core [2024-11-22 01:22:31,318 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:22:31,569 INFO L134 CoverageAnalysis]: Checked inductivity of 240 backedges. 26 proven. 19 refuted. 0 times theorem prover too weak. 195 trivial. 0 not checked. [2024-11-22 01:22:31,569 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-22 01:22:31,813 INFO L134 CoverageAnalysis]: Checked inductivity of 240 backedges. 22 proven. 14 refuted. 0 times theorem prover too weak. 204 trivial. 0 not checked. [2024-11-22 01:22:31,813 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:22:31,813 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1255045792] [2024-11-22 01:22:31,813 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-22 01:22:31,813 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [157490353] [2024-11-22 01:22:31,814 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [157490353] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-22 01:22:31,814 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-22 01:22:31,814 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 10] total 22 [2024-11-22 01:22:31,814 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1054323603] [2024-11-22 01:22:31,814 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-22 01:22:31,814 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-11-22 01:22:31,815 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:22:31,815 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-22 01:22:31,816 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=89, Invalid=373, Unknown=0, NotChecked=0, Total=462 [2024-11-22 01:22:31,816 INFO L87 Difference]: Start difference. First operand 449 states and 641 transitions. Second operand has 22 states, 22 states have (on average 1.9545454545454546) internal successors, (43), 19 states have internal predecessors, (43), 8 states have call successors, (27), 3 states have call predecessors, (27), 2 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) [2024-11-22 01:22:33,538 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:22:33,538 INFO L93 Difference]: Finished difference Result 991 states and 1551 transitions. [2024-11-22 01:22:33,539 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2024-11-22 01:22:33,539 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 1.9545454545454546) internal successors, (43), 19 states have internal predecessors, (43), 8 states have call successors, (27), 3 states have call predecessors, (27), 2 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) Word has length 90 [2024-11-22 01:22:33,539 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:22:33,544 INFO L225 Difference]: With dead ends: 991 [2024-11-22 01:22:33,544 INFO L226 Difference]: Without dead ends: 989 [2024-11-22 01:22:33,545 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 206 GetRequests, 159 SyntacticMatches, 0 SemanticMatches, 47 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 561 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=528, Invalid=1824, Unknown=0, NotChecked=0, Total=2352 [2024-11-22 01:22:33,545 INFO L432 NwaCegarLoop]: 44 mSDtfsCounter, 156 mSDsluCounter, 385 mSDsCounter, 0 mSdLazyCounter, 455 mSolverCounterSat, 136 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 160 SdHoareTripleChecker+Valid, 429 SdHoareTripleChecker+Invalid, 591 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 136 IncrementalHoareTripleChecker+Valid, 455 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-11-22 01:22:33,546 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [160 Valid, 429 Invalid, 591 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [136 Valid, 455 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-11-22 01:22:33,546 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 989 states. [2024-11-22 01:22:34,173 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 989 to 828. [2024-11-22 01:22:34,175 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 828 states, 429 states have (on average 1.2913752913752914) internal successors, (554), 430 states have internal predecessors, (554), 373 states have call successors, (373), 25 states have call predecessors, (373), 25 states have return successors, (372), 372 states have call predecessors, (372), 372 states have call successors, (372) [2024-11-22 01:22:34,178 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 828 states to 828 states and 1299 transitions. [2024-11-22 01:22:34,180 INFO L78 Accepts]: Start accepts. Automaton has 828 states and 1299 transitions. Word has length 90 [2024-11-22 01:22:34,180 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:22:34,180 INFO L471 AbstractCegarLoop]: Abstraction has 828 states and 1299 transitions. [2024-11-22 01:22:34,181 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 1.9545454545454546) internal successors, (43), 19 states have internal predecessors, (43), 8 states have call successors, (27), 3 states have call predecessors, (27), 2 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) [2024-11-22 01:22:34,181 INFO L276 IsEmpty]: Start isEmpty. Operand 828 states and 1299 transitions. [2024-11-22 01:22:34,181 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2024-11-22 01:22:34,182 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:22:34,182 INFO L215 NwaCegarLoop]: trace histogram [10, 9, 9, 4, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:22:34,189 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Ended with exit code 0 [2024-11-22 01:22:34,385 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2024-11-22 01:22:34,386 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:22:34,386 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:22:34,386 INFO L85 PathProgramCache]: Analyzing trace with hash 1599365144, now seen corresponding path program 1 times [2024-11-22 01:22:34,386 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:22:34,386 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [461558007] [2024-11-22 01:22:34,386 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:22:34,386 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:22:34,418 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-22 01:22:34,419 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [299690236] [2024-11-22 01:22:34,419 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:22:34,419 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:22:34,419 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:22:34,423 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-22 01:22:34,424 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2024-11-22 01:22:34,471 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:22:34,475 INFO L255 TraceCheckSpWp]: Trace formula consists of 214 conjuncts, 47 conjuncts are in the unsatisfiable core [2024-11-22 01:22:34,478 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:22:35,059 INFO L134 CoverageAnalysis]: Checked inductivity of 206 backedges. 24 proven. 23 refuted. 0 times theorem prover too weak. 159 trivial. 0 not checked. [2024-11-22 01:22:35,060 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-22 01:22:35,516 INFO L134 CoverageAnalysis]: Checked inductivity of 206 backedges. 18 proven. 20 refuted. 0 times theorem prover too weak. 168 trivial. 0 not checked. [2024-11-22 01:22:35,516 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:22:35,516 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [461558007] [2024-11-22 01:22:35,516 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-22 01:22:35,516 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [299690236] [2024-11-22 01:22:35,517 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [299690236] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-22 01:22:35,517 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-22 01:22:35,517 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 23 [2024-11-22 01:22:35,517 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [625466650] [2024-11-22 01:22:35,517 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-22 01:22:35,518 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-11-22 01:22:35,518 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:22:35,518 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-22 01:22:35,518 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=80, Invalid=426, Unknown=0, NotChecked=0, Total=506 [2024-11-22 01:22:35,519 INFO L87 Difference]: Start difference. First operand 828 states and 1299 transitions. Second operand has 23 states, 23 states have (on average 2.3043478260869565) internal successors, (53), 20 states have internal predecessors, (53), 8 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2024-11-22 01:22:41,037 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:22:41,037 INFO L93 Difference]: Finished difference Result 1111 states and 1744 transitions. [2024-11-22 01:22:41,037 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 44 states. [2024-11-22 01:22:41,038 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 2.3043478260869565) internal successors, (53), 20 states have internal predecessors, (53), 8 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) Word has length 90 [2024-11-22 01:22:41,038 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:22:41,043 INFO L225 Difference]: With dead ends: 1111 [2024-11-22 01:22:41,043 INFO L226 Difference]: Without dead ends: 1109 [2024-11-22 01:22:41,044 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 215 GetRequests, 157 SyntacticMatches, 0 SemanticMatches, 58 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 766 ImplicationChecksByTransitivity, 2.7s TimeCoverageRelationStatistics Valid=711, Invalid=2829, Unknown=0, NotChecked=0, Total=3540 [2024-11-22 01:22:41,045 INFO L432 NwaCegarLoop]: 52 mSDtfsCounter, 166 mSDsluCounter, 572 mSDsCounter, 0 mSdLazyCounter, 896 mSolverCounterSat, 148 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 166 SdHoareTripleChecker+Valid, 624 SdHoareTripleChecker+Invalid, 1044 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 148 IncrementalHoareTripleChecker+Valid, 896 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.2s IncrementalHoareTripleChecker+Time [2024-11-22 01:22:41,045 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [166 Valid, 624 Invalid, 1044 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [148 Valid, 896 Invalid, 0 Unknown, 0 Unchecked, 2.2s Time] [2024-11-22 01:22:41,046 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1109 states. [2024-11-22 01:22:42,000 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1109 to 1024. [2024-11-22 01:22:42,001 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1024 states, 529 states have (on average 1.2967863894139886) internal successors, (686), 530 states have internal predecessors, (686), 465 states have call successors, (465), 29 states have call predecessors, (465), 29 states have return successors, (464), 464 states have call predecessors, (464), 464 states have call successors, (464) [2024-11-22 01:22:42,005 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1024 states to 1024 states and 1615 transitions. [2024-11-22 01:22:42,006 INFO L78 Accepts]: Start accepts. Automaton has 1024 states and 1615 transitions. Word has length 90 [2024-11-22 01:22:42,006 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:22:42,006 INFO L471 AbstractCegarLoop]: Abstraction has 1024 states and 1615 transitions. [2024-11-22 01:22:42,007 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 2.3043478260869565) internal successors, (53), 20 states have internal predecessors, (53), 8 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2024-11-22 01:22:42,007 INFO L276 IsEmpty]: Start isEmpty. Operand 1024 states and 1615 transitions. [2024-11-22 01:22:42,008 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 96 [2024-11-22 01:22:42,008 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:22:42,008 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 5, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:22:42,016 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Ended with exit code 0 [2024-11-22 01:22:42,209 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2024-11-22 01:22:42,209 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:22:42,209 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:22:42,209 INFO L85 PathProgramCache]: Analyzing trace with hash -1330396859, now seen corresponding path program 2 times [2024-11-22 01:22:42,209 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:22:42,209 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1852401646] [2024-11-22 01:22:42,210 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-22 01:22:42,210 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:22:42,219 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-22 01:22:42,219 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-22 01:22:42,337 INFO L134 CoverageAnalysis]: Checked inductivity of 194 backedges. 38 proven. 16 refuted. 0 times theorem prover too weak. 140 trivial. 0 not checked. [2024-11-22 01:22:42,338 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:22:42,338 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1852401646] [2024-11-22 01:22:42,338 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1852401646] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-22 01:22:42,338 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1952407613] [2024-11-22 01:22:42,338 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-22 01:22:42,338 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:22:42,338 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:22:42,340 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-22 01:22:42,342 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2024-11-22 01:22:42,386 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-22 01:22:42,386 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-22 01:22:42,387 INFO L255 TraceCheckSpWp]: Trace formula consists of 241 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-22 01:22:42,389 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:22:42,453 INFO L134 CoverageAnalysis]: Checked inductivity of 194 backedges. 38 proven. 16 refuted. 0 times theorem prover too weak. 140 trivial. 0 not checked. [2024-11-22 01:22:42,453 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-22 01:22:42,550 INFO L134 CoverageAnalysis]: Checked inductivity of 194 backedges. 38 proven. 16 refuted. 0 times theorem prover too weak. 140 trivial. 0 not checked. [2024-11-22 01:22:42,550 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1952407613] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-22 01:22:42,550 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-22 01:22:42,550 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10, 10] total 13 [2024-11-22 01:22:42,551 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [377417194] [2024-11-22 01:22:42,551 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-22 01:22:42,551 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-22 01:22:42,551 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:22:42,552 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-22 01:22:42,552 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=129, Unknown=0, NotChecked=0, Total=156 [2024-11-22 01:22:42,552 INFO L87 Difference]: Start difference. First operand 1024 states and 1615 transitions. Second operand has 13 states, 13 states have (on average 3.4615384615384617) internal successors, (45), 13 states have internal predecessors, (45), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2024-11-22 01:22:43,997 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:22:43,997 INFO L93 Difference]: Finished difference Result 1136 states and 1784 transitions. [2024-11-22 01:22:43,998 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-11-22 01:22:43,998 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 3.4615384615384617) internal successors, (45), 13 states have internal predecessors, (45), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) Word has length 95 [2024-11-22 01:22:43,998 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:22:44,007 INFO L225 Difference]: With dead ends: 1136 [2024-11-22 01:22:44,011 INFO L226 Difference]: Without dead ends: 1129 [2024-11-22 01:22:44,012 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 224 GetRequests, 187 SyntacticMatches, 8 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 164 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=214, Invalid=716, Unknown=0, NotChecked=0, Total=930 [2024-11-22 01:22:44,012 INFO L432 NwaCegarLoop]: 57 mSDtfsCounter, 92 mSDsluCounter, 330 mSDsCounter, 0 mSdLazyCounter, 257 mSolverCounterSat, 88 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 96 SdHoareTripleChecker+Valid, 387 SdHoareTripleChecker+Invalid, 345 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 88 IncrementalHoareTripleChecker+Valid, 257 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-22 01:22:44,012 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [96 Valid, 387 Invalid, 345 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [88 Valid, 257 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-22 01:22:44,013 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1129 states. [2024-11-22 01:22:44,904 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1129 to 993. [2024-11-22 01:22:44,905 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 993 states, 506 states have (on average 1.3043478260869565) internal successors, (660), 507 states have internal predecessors, (660), 457 states have call successors, (457), 29 states have call predecessors, (457), 29 states have return successors, (456), 456 states have call predecessors, (456), 456 states have call successors, (456) [2024-11-22 01:22:44,908 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 993 states to 993 states and 1573 transitions. [2024-11-22 01:22:44,910 INFO L78 Accepts]: Start accepts. Automaton has 993 states and 1573 transitions. Word has length 95 [2024-11-22 01:22:44,910 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:22:44,910 INFO L471 AbstractCegarLoop]: Abstraction has 993 states and 1573 transitions. [2024-11-22 01:22:44,910 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 3.4615384615384617) internal successors, (45), 13 states have internal predecessors, (45), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2024-11-22 01:22:44,911 INFO L276 IsEmpty]: Start isEmpty. Operand 993 states and 1573 transitions. [2024-11-22 01:22:44,911 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 99 [2024-11-22 01:22:44,912 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:22:44,912 INFO L215 NwaCegarLoop]: trace histogram [10, 9, 9, 5, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:22:44,919 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Ended with exit code 0 [2024-11-22 01:22:45,113 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:22:45,113 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:22:45,113 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:22:45,114 INFO L85 PathProgramCache]: Analyzing trace with hash -577787487, now seen corresponding path program 4 times [2024-11-22 01:22:45,114 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:22:45,114 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1417214200] [2024-11-22 01:22:45,114 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-22 01:22:45,114 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:22:45,153 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-22 01:22:45,153 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-22 01:22:45,154 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1251776812] [2024-11-22 01:22:45,154 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-22 01:22:45,154 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:22:45,154 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:22:45,156 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-22 01:22:45,158 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2024-11-22 01:22:45,220 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-22 01:22:45,220 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-22 01:22:45,222 INFO L255 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 60 conjuncts are in the unsatisfiable core [2024-11-22 01:22:45,225 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:22:46,000 INFO L134 CoverageAnalysis]: Checked inductivity of 226 backedges. 18 proven. 40 refuted. 0 times theorem prover too weak. 168 trivial. 0 not checked. [2024-11-22 01:22:46,000 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-22 01:22:46,790 INFO L134 CoverageAnalysis]: Checked inductivity of 226 backedges. 20 proven. 38 refuted. 0 times theorem prover too weak. 168 trivial. 0 not checked. [2024-11-22 01:22:46,791 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:22:46,791 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1417214200] [2024-11-22 01:22:46,791 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-22 01:22:46,791 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1251776812] [2024-11-22 01:22:46,791 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1251776812] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-22 01:22:46,791 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-22 01:22:46,791 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 16] total 27 [2024-11-22 01:22:46,791 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1273906880] [2024-11-22 01:22:46,792 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-22 01:22:46,792 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2024-11-22 01:22:46,792 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:22:46,792 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2024-11-22 01:22:46,793 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=112, Invalid=590, Unknown=0, NotChecked=0, Total=702 [2024-11-22 01:22:46,793 INFO L87 Difference]: Start difference. First operand 993 states and 1573 transitions. Second operand has 27 states, 27 states have (on average 2.3703703703703702) internal successors, (64), 26 states have internal predecessors, (64), 7 states have call successors, (24), 2 states have call predecessors, (24), 1 states have return successors, (22), 7 states have call predecessors, (22), 7 states have call successors, (22) [2024-11-22 01:22:56,345 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:22:56,346 INFO L93 Difference]: Finished difference Result 1287 states and 2017 transitions. [2024-11-22 01:22:56,346 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2024-11-22 01:22:56,346 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 27 states have (on average 2.3703703703703702) internal successors, (64), 26 states have internal predecessors, (64), 7 states have call successors, (24), 2 states have call predecessors, (24), 1 states have return successors, (22), 7 states have call predecessors, (22), 7 states have call successors, (22) Word has length 98 [2024-11-22 01:22:56,347 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:22:56,359 INFO L225 Difference]: With dead ends: 1287 [2024-11-22 01:22:56,360 INFO L226 Difference]: Without dead ends: 1285 [2024-11-22 01:22:56,364 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 229 GetRequests, 166 SyntacticMatches, 3 SemanticMatches, 60 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 793 ImplicationChecksByTransitivity, 7.0s TimeCoverageRelationStatistics Valid=764, Invalid=3018, Unknown=0, NotChecked=0, Total=3782 [2024-11-22 01:22:56,365 INFO L432 NwaCegarLoop]: 47 mSDtfsCounter, 203 mSDsluCounter, 487 mSDsCounter, 0 mSdLazyCounter, 603 mSolverCounterSat, 214 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 207 SdHoareTripleChecker+Valid, 534 SdHoareTripleChecker+Invalid, 817 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 214 IncrementalHoareTripleChecker+Valid, 603 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.9s IncrementalHoareTripleChecker+Time [2024-11-22 01:22:56,365 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [207 Valid, 534 Invalid, 817 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [214 Valid, 603 Invalid, 0 Unknown, 0 Unchecked, 1.9s Time] [2024-11-22 01:22:56,367 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1285 states. [2024-11-22 01:22:57,605 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1285 to 1179. [2024-11-22 01:22:57,607 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1179 states, 604 states have (on average 1.2980132450331126) internal successors, (784), 605 states have internal predecessors, (784), 537 states have call successors, (537), 37 states have call predecessors, (537), 37 states have return successors, (536), 536 states have call predecessors, (536), 536 states have call successors, (536) [2024-11-22 01:22:57,611 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1179 states to 1179 states and 1857 transitions. [2024-11-22 01:22:57,613 INFO L78 Accepts]: Start accepts. Automaton has 1179 states and 1857 transitions. Word has length 98 [2024-11-22 01:22:57,614 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:22:57,614 INFO L471 AbstractCegarLoop]: Abstraction has 1179 states and 1857 transitions. [2024-11-22 01:22:57,614 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 27 states have (on average 2.3703703703703702) internal successors, (64), 26 states have internal predecessors, (64), 7 states have call successors, (24), 2 states have call predecessors, (24), 1 states have return successors, (22), 7 states have call predecessors, (22), 7 states have call successors, (22) [2024-11-22 01:22:57,614 INFO L276 IsEmpty]: Start isEmpty. Operand 1179 states and 1857 transitions. [2024-11-22 01:22:57,615 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 105 [2024-11-22 01:22:57,616 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:22:57,616 INFO L215 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:22:57,622 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2024-11-22 01:22:57,819 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:22:57,820 INFO L396 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:22:57,820 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:22:57,820 INFO L85 PathProgramCache]: Analyzing trace with hash 1084123749, now seen corresponding path program 2 times [2024-11-22 01:22:57,820 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:22:57,820 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [854738247] [2024-11-22 01:22:57,821 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-22 01:22:57,821 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:22:57,833 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-22 01:22:57,833 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-22 01:22:57,834 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [53211466] [2024-11-22 01:22:57,834 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-22 01:22:57,834 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:22:57,834 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:22:57,836 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-22 01:22:57,837 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2024-11-22 01:22:57,893 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-22 01:22:57,893 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-22 01:22:57,895 INFO L255 TraceCheckSpWp]: Trace formula consists of 237 conjuncts, 49 conjuncts are in the unsatisfiable core [2024-11-22 01:22:57,897 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:22:58,411 INFO L134 CoverageAnalysis]: Checked inductivity of 334 backedges. 24 proven. 22 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2024-11-22 01:22:58,412 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-22 01:22:58,774 INFO L134 CoverageAnalysis]: Checked inductivity of 334 backedges. 24 proven. 22 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2024-11-22 01:22:58,774 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:22:58,774 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [854738247] [2024-11-22 01:22:58,774 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-22 01:22:58,774 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [53211466] [2024-11-22 01:22:58,774 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [53211466] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-22 01:22:58,775 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-22 01:22:58,775 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 20 [2024-11-22 01:22:58,775 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1717976164] [2024-11-22 01:22:58,775 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-22 01:22:58,775 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-11-22 01:22:58,780 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:22:58,781 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-11-22 01:22:58,781 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=314, Unknown=0, NotChecked=0, Total=380 [2024-11-22 01:22:58,781 INFO L87 Difference]: Start difference. First operand 1179 states and 1857 transitions. Second operand has 20 states, 18 states have (on average 2.5555555555555554) internal successors, (46), 19 states have internal predecessors, (46), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) [2024-11-22 01:23:04,719 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:23:04,720 INFO L93 Difference]: Finished difference Result 1460 states and 2294 transitions. [2024-11-22 01:23:04,726 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 51 states. [2024-11-22 01:23:04,727 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 18 states have (on average 2.5555555555555554) internal successors, (46), 19 states have internal predecessors, (46), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) Word has length 104 [2024-11-22 01:23:04,727 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:23:04,736 INFO L225 Difference]: With dead ends: 1460 [2024-11-22 01:23:04,740 INFO L226 Difference]: Without dead ends: 1452 [2024-11-22 01:23:04,741 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 249 GetRequests, 186 SyntacticMatches, 2 SemanticMatches, 61 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 963 ImplicationChecksByTransitivity, 3.4s TimeCoverageRelationStatistics Valid=778, Invalid=3128, Unknown=0, NotChecked=0, Total=3906 [2024-11-22 01:23:04,742 INFO L432 NwaCegarLoop]: 68 mSDtfsCounter, 170 mSDsluCounter, 648 mSDsCounter, 0 mSdLazyCounter, 938 mSolverCounterSat, 161 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 182 SdHoareTripleChecker+Valid, 716 SdHoareTripleChecker+Invalid, 1099 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 161 IncrementalHoareTripleChecker+Valid, 938 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.3s IncrementalHoareTripleChecker+Time [2024-11-22 01:23:04,742 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [182 Valid, 716 Invalid, 1099 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [161 Valid, 938 Invalid, 0 Unknown, 0 Unchecked, 1.3s Time] [2024-11-22 01:23:04,743 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1452 states. [2024-11-22 01:23:06,138 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1452 to 1333. [2024-11-22 01:23:06,140 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1333 states, 689 states have (on average 1.2960812772133528) internal successors, (893), 690 states have internal predecessors, (893), 601 states have call successors, (601), 42 states have call predecessors, (601), 42 states have return successors, (600), 600 states have call predecessors, (600), 600 states have call successors, (600) [2024-11-22 01:23:06,144 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1333 states to 1333 states and 2094 transitions. [2024-11-22 01:23:06,146 INFO L78 Accepts]: Start accepts. Automaton has 1333 states and 2094 transitions. Word has length 104 [2024-11-22 01:23:06,146 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:23:06,146 INFO L471 AbstractCegarLoop]: Abstraction has 1333 states and 2094 transitions. [2024-11-22 01:23:06,146 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 18 states have (on average 2.5555555555555554) internal successors, (46), 19 states have internal predecessors, (46), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) [2024-11-22 01:23:06,146 INFO L276 IsEmpty]: Start isEmpty. Operand 1333 states and 2094 transitions. [2024-11-22 01:23:06,149 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2024-11-22 01:23:06,149 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:23:06,150 INFO L215 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:23:06,159 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Ended with exit code 0 [2024-11-22 01:23:06,350 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20,20 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:23:06,351 INFO L396 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:23:06,352 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:23:06,352 INFO L85 PathProgramCache]: Analyzing trace with hash 2024025072, now seen corresponding path program 3 times [2024-11-22 01:23:06,352 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:23:06,352 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1976041601] [2024-11-22 01:23:06,352 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-22 01:23:06,352 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:23:06,384 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 8 check-sat command(s) [2024-11-22 01:23:06,385 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-22 01:23:06,385 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [609238638] [2024-11-22 01:23:06,386 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-22 01:23:06,386 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:23:06,386 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:23:06,391 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-22 01:23:06,392 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2024-11-22 01:23:06,446 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2024-11-22 01:23:06,446 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-22 01:23:06,451 INFO L255 TraceCheckSpWp]: Trace formula consists of 189 conjuncts, 53 conjuncts are in the unsatisfiable core [2024-11-22 01:23:06,453 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:23:07,106 INFO L134 CoverageAnalysis]: Checked inductivity of 339 backedges. 24 proven. 27 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2024-11-22 01:23:07,106 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-22 01:23:07,882 INFO L134 CoverageAnalysis]: Checked inductivity of 339 backedges. 24 proven. 27 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2024-11-22 01:23:07,882 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:23:07,882 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1976041601] [2024-11-22 01:23:07,882 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-22 01:23:07,882 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [609238638] [2024-11-22 01:23:07,882 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [609238638] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-22 01:23:07,882 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-22 01:23:07,882 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 24 [2024-11-22 01:23:07,883 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [959008561] [2024-11-22 01:23:07,883 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-22 01:23:07,883 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2024-11-22 01:23:07,883 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:23:07,883 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2024-11-22 01:23:07,884 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=88, Invalid=464, Unknown=0, NotChecked=0, Total=552 [2024-11-22 01:23:07,884 INFO L87 Difference]: Start difference. First operand 1333 states and 2094 transitions. Second operand has 24 states, 22 states have (on average 2.3636363636363638) internal successors, (52), 23 states have internal predecessors, (52), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) [2024-11-22 01:23:14,171 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:23:14,172 INFO L93 Difference]: Finished difference Result 1546 states and 2424 transitions. [2024-11-22 01:23:14,173 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 58 states. [2024-11-22 01:23:14,173 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 22 states have (on average 2.3636363636363638) internal successors, (52), 23 states have internal predecessors, (52), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) Word has length 107 [2024-11-22 01:23:14,173 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:23:14,181 INFO L225 Difference]: With dead ends: 1546 [2024-11-22 01:23:14,181 INFO L226 Difference]: Without dead ends: 1538 [2024-11-22 01:23:14,183 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 262 GetRequests, 188 SyntacticMatches, 2 SemanticMatches, 72 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1473 ImplicationChecksByTransitivity, 4.0s TimeCoverageRelationStatistics Valid=975, Invalid=4427, Unknown=0, NotChecked=0, Total=5402 [2024-11-22 01:23:14,184 INFO L432 NwaCegarLoop]: 51 mSDtfsCounter, 195 mSDsluCounter, 620 mSDsCounter, 0 mSdLazyCounter, 800 mSolverCounterSat, 202 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 195 SdHoareTripleChecker+Valid, 671 SdHoareTripleChecker+Invalid, 1002 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 202 IncrementalHoareTripleChecker+Valid, 800 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.1s IncrementalHoareTripleChecker+Time [2024-11-22 01:23:14,184 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [195 Valid, 671 Invalid, 1002 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [202 Valid, 800 Invalid, 0 Unknown, 0 Unchecked, 1.1s Time] [2024-11-22 01:23:14,185 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1538 states. [2024-11-22 01:23:15,688 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1538 to 1420. [2024-11-22 01:23:15,690 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1420 states, 731 states have (on average 1.2982216142270862) internal successors, (949), 732 states have internal predecessors, (949), 645 states have call successors, (645), 43 states have call predecessors, (645), 43 states have return successors, (644), 644 states have call predecessors, (644), 644 states have call successors, (644) [2024-11-22 01:23:15,693 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1420 states to 1420 states and 2238 transitions. [2024-11-22 01:23:15,695 INFO L78 Accepts]: Start accepts. Automaton has 1420 states and 2238 transitions. Word has length 107 [2024-11-22 01:23:15,696 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:23:15,696 INFO L471 AbstractCegarLoop]: Abstraction has 1420 states and 2238 transitions. [2024-11-22 01:23:15,696 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 22 states have (on average 2.3636363636363638) internal successors, (52), 23 states have internal predecessors, (52), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) [2024-11-22 01:23:15,696 INFO L276 IsEmpty]: Start isEmpty. Operand 1420 states and 2238 transitions. [2024-11-22 01:23:15,697 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 118 [2024-11-22 01:23:15,698 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:23:15,698 INFO L215 NwaCegarLoop]: trace histogram [14, 13, 13, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:23:15,712 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Ended with exit code 0 [2024-11-22 01:23:15,898 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 21 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable21 [2024-11-22 01:23:15,898 INFO L396 AbstractCegarLoop]: === Iteration 23 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:23:15,898 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:23:15,899 INFO L85 PathProgramCache]: Analyzing trace with hash -1454845263, now seen corresponding path program 2 times [2024-11-22 01:23:15,899 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:23:15,899 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1240167222] [2024-11-22 01:23:15,899 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-22 01:23:15,899 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:23:15,927 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-22 01:23:15,931 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-22 01:23:15,939 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1467618892] [2024-11-22 01:23:15,940 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-22 01:23:15,940 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:23:15,940 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:23:15,946 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-22 01:23:15,948 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Waiting until timeout for monitored process [2024-11-22 01:23:16,042 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-22 01:23:16,042 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-22 01:23:16,043 INFO L255 TraceCheckSpWp]: Trace formula consists of 276 conjuncts, 73 conjuncts are in the unsatisfiable core [2024-11-22 01:23:16,045 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:23:17,036 INFO L134 CoverageAnalysis]: Checked inductivity of 408 backedges. 58 proven. 59 refuted. 0 times theorem prover too weak. 291 trivial. 0 not checked. [2024-11-22 01:23:17,036 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-22 01:23:18,310 INFO L134 CoverageAnalysis]: Checked inductivity of 408 backedges. 56 proven. 52 refuted. 0 times theorem prover too weak. 300 trivial. 0 not checked. [2024-11-22 01:23:18,310 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:23:18,310 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1240167222] [2024-11-22 01:23:18,310 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-22 01:23:18,310 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1467618892] [2024-11-22 01:23:18,311 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1467618892] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-22 01:23:18,311 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-22 01:23:18,311 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 17] total 34 [2024-11-22 01:23:18,311 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1390090554] [2024-11-22 01:23:18,311 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-22 01:23:18,311 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 34 states [2024-11-22 01:23:18,312 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:23:18,312 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2024-11-22 01:23:18,313 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=168, Invalid=954, Unknown=0, NotChecked=0, Total=1122 [2024-11-22 01:23:18,313 INFO L87 Difference]: Start difference. First operand 1420 states and 2238 transitions. Second operand has 34 states, 34 states have (on average 2.1176470588235294) internal successors, (72), 32 states have internal predecessors, (72), 11 states have call successors, (33), 3 states have call predecessors, (33), 3 states have return successors, (32), 11 states have call predecessors, (32), 11 states have call successors, (32) [2024-11-22 01:23:32,450 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:23:32,451 INFO L93 Difference]: Finished difference Result 1666 states and 2583 transitions. [2024-11-22 01:23:32,451 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 63 states. [2024-11-22 01:23:32,452 INFO L78 Accepts]: Start accepts. Automaton has has 34 states, 34 states have (on average 2.1176470588235294) internal successors, (72), 32 states have internal predecessors, (72), 11 states have call successors, (33), 3 states have call predecessors, (33), 3 states have return successors, (32), 11 states have call predecessors, (32), 11 states have call successors, (32) Word has length 117 [2024-11-22 01:23:32,452 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:23:32,460 INFO L225 Difference]: With dead ends: 1666 [2024-11-22 01:23:32,460 INFO L226 Difference]: Without dead ends: 1664 [2024-11-22 01:23:32,463 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 285 GetRequests, 200 SyntacticMatches, 0 SemanticMatches, 85 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1828 ImplicationChecksByTransitivity, 8.4s TimeCoverageRelationStatistics Valid=1422, Invalid=6060, Unknown=0, NotChecked=0, Total=7482 [2024-11-22 01:23:32,463 INFO L432 NwaCegarLoop]: 60 mSDtfsCounter, 244 mSDsluCounter, 967 mSDsCounter, 0 mSdLazyCounter, 1586 mSolverCounterSat, 280 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 244 SdHoareTripleChecker+Valid, 1027 SdHoareTripleChecker+Invalid, 1866 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 280 IncrementalHoareTripleChecker+Valid, 1586 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.3s IncrementalHoareTripleChecker+Time [2024-11-22 01:23:32,464 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [244 Valid, 1027 Invalid, 1866 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [280 Valid, 1586 Invalid, 0 Unknown, 0 Unchecked, 4.3s Time] [2024-11-22 01:23:32,465 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1664 states. [2024-11-22 01:23:34,419 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1664 to 1547. [2024-11-22 01:23:34,421 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1547 states, 821 states have (on average 1.2886723507917175) internal successors, (1058), 825 states have internal predecessors, (1058), 675 states have call successors, (675), 50 states have call predecessors, (675), 50 states have return successors, (674), 671 states have call predecessors, (674), 674 states have call successors, (674) [2024-11-22 01:23:34,425 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1547 states to 1547 states and 2407 transitions. [2024-11-22 01:23:34,427 INFO L78 Accepts]: Start accepts. Automaton has 1547 states and 2407 transitions. Word has length 117 [2024-11-22 01:23:34,427 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:23:34,427 INFO L471 AbstractCegarLoop]: Abstraction has 1547 states and 2407 transitions. [2024-11-22 01:23:34,427 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 34 states, 34 states have (on average 2.1176470588235294) internal successors, (72), 32 states have internal predecessors, (72), 11 states have call successors, (33), 3 states have call predecessors, (33), 3 states have return successors, (32), 11 states have call predecessors, (32), 11 states have call successors, (32) [2024-11-22 01:23:34,427 INFO L276 IsEmpty]: Start isEmpty. Operand 1547 states and 2407 transitions. [2024-11-22 01:23:34,428 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 118 [2024-11-22 01:23:34,428 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:23:34,429 INFO L215 NwaCegarLoop]: trace histogram [13, 12, 12, 5, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:23:34,435 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Forceful destruction successful, exit code 0 [2024-11-22 01:23:34,629 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 22 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable22 [2024-11-22 01:23:34,629 INFO L396 AbstractCegarLoop]: === Iteration 24 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:23:34,630 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:23:34,630 INFO L85 PathProgramCache]: Analyzing trace with hash 1746474790, now seen corresponding path program 4 times [2024-11-22 01:23:34,630 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:23:34,630 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2029020992] [2024-11-22 01:23:34,630 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-22 01:23:34,630 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:23:34,655 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-22 01:23:34,656 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-22 01:23:34,656 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1952224400] [2024-11-22 01:23:34,656 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-22 01:23:34,657 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:23:34,657 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:23:34,658 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-22 01:23:34,659 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Waiting until timeout for monitored process [2024-11-22 01:23:34,729 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-22 01:23:34,729 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-22 01:23:34,731 INFO L255 TraceCheckSpWp]: Trace formula consists of 252 conjuncts, 102 conjuncts are in the unsatisfiable core [2024-11-22 01:23:34,733 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:23:35,907 INFO L134 CoverageAnalysis]: Checked inductivity of 366 backedges. 55 proven. 92 refuted. 0 times theorem prover too weak. 219 trivial. 0 not checked. [2024-11-22 01:23:35,907 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-22 01:23:36,722 INFO L134 CoverageAnalysis]: Checked inductivity of 366 backedges. 77 proven. 57 refuted. 0 times theorem prover too weak. 232 trivial. 0 not checked. [2024-11-22 01:23:36,722 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:23:36,722 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2029020992] [2024-11-22 01:23:36,722 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-22 01:23:36,723 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1952224400] [2024-11-22 01:23:36,723 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1952224400] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-22 01:23:36,723 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-22 01:23:36,723 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 16] total 37 [2024-11-22 01:23:36,723 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [426315785] [2024-11-22 01:23:36,723 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-22 01:23:36,723 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 37 states [2024-11-22 01:23:36,727 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:23:36,728 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2024-11-22 01:23:36,728 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=188, Invalid=1144, Unknown=0, NotChecked=0, Total=1332 [2024-11-22 01:23:36,728 INFO L87 Difference]: Start difference. First operand 1547 states and 2407 transitions. Second operand has 37 states, 35 states have (on average 2.257142857142857) internal successors, (79), 34 states have internal predecessors, (79), 11 states have call successors, (31), 3 states have call predecessors, (31), 3 states have return successors, (30), 9 states have call predecessors, (30), 9 states have call successors, (30)