./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound50.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 3061b6dc Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound50.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 5506d4c7458a400c41a33af3f6404f1e04b9f2e97e99f1fb53b74acf6bf59baf --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.dk.eval-assert-order-craig-3061b6d-m [2024-11-18 13:46:45,378 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-18 13:46:45,451 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-18 13:46:45,456 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-18 13:46:45,457 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-18 13:46:45,482 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-18 13:46:45,484 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-18 13:46:45,484 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-18 13:46:45,485 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-18 13:46:45,488 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-18 13:46:45,489 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-18 13:46:45,489 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-18 13:46:45,489 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-18 13:46:45,490 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-18 13:46:45,490 INFO L153 SettingsManager]: * Use SBE=true [2024-11-18 13:46:45,490 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-18 13:46:45,490 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-18 13:46:45,490 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-18 13:46:45,490 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-18 13:46:45,491 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-18 13:46:45,491 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-18 13:46:45,492 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-18 13:46:45,492 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-18 13:46:45,493 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-18 13:46:45,493 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-18 13:46:45,493 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-18 13:46:45,493 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-18 13:46:45,493 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-18 13:46:45,494 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-18 13:46:45,494 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-18 13:46:45,494 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-18 13:46:45,494 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-18 13:46:45,494 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-18 13:46:45,495 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-18 13:46:45,495 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-18 13:46:45,495 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-18 13:46:45,496 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-18 13:46:45,496 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-18 13:46:45,497 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-18 13:46:45,497 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-18 13:46:45,497 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-18 13:46:45,497 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-18 13:46:45,497 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 -> 5506d4c7458a400c41a33af3f6404f1e04b9f2e97e99f1fb53b74acf6bf59baf [2024-11-18 13:46:45,686 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-18 13:46:45,705 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-18 13:46:45,708 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-18 13:46:45,709 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-18 13:46:45,709 INFO L274 PluginConnector]: CDTParser initialized [2024-11-18 13:46:45,710 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound50.c [2024-11-18 13:46:46,967 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-18 13:46:47,106 INFO L384 CDTParser]: Found 1 translation units. [2024-11-18 13:46:47,107 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound50.c [2024-11-18 13:46:47,112 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/c35c55351/56df4f80d2fa4035a6fa502d98831844/FLAGcbf71c09f [2024-11-18 13:46:47,122 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/c35c55351/56df4f80d2fa4035a6fa502d98831844 [2024-11-18 13:46:47,124 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-18 13:46:47,125 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-18 13:46:47,126 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-18 13:46:47,126 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-18 13:46:47,130 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-18 13:46:47,131 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 18.11 01:46:47" (1/1) ... [2024-11-18 13:46:47,131 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@66764ee1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:46:47, skipping insertion in model container [2024-11-18 13:46:47,132 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 18.11 01:46:47" (1/1) ... [2024-11-18 13:46:47,149 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-18 13:46:47,302 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/hard2_unwindbound50.c[526,539] [2024-11-18 13:46:47,313 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-18 13:46:47,319 INFO L200 MainTranslator]: Completed pre-run [2024-11-18 13:46:47,329 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/hard2_unwindbound50.c[526,539] [2024-11-18 13:46:47,333 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-18 13:46:47,345 INFO L204 MainTranslator]: Completed translation [2024-11-18 13:46:47,346 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:46:47 WrapperNode [2024-11-18 13:46:47,346 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-18 13:46:47,347 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-18 13:46:47,347 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-18 13:46:47,347 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-18 13:46:47,352 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:46:47" (1/1) ... [2024-11-18 13:46:47,357 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:46:47" (1/1) ... [2024-11-18 13:46:47,373 INFO L138 Inliner]: procedures = 14, calls = 22, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 69 [2024-11-18 13:46:47,373 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-18 13:46:47,374 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-18 13:46:47,374 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-18 13:46:47,374 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-18 13:46:47,382 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:46:47" (1/1) ... [2024-11-18 13:46:47,382 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:46:47" (1/1) ... [2024-11-18 13:46:47,389 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:46:47" (1/1) ... [2024-11-18 13:46:47,398 INFO L175 MemorySlicer]: Split 10 memory accesses to 2 slices as follows [2, 8]. 80 percent of accesses are in the largest equivalence class. The 10 initializations are split as follows [2, 8]. The 0 writes are split as follows [0, 0]. [2024-11-18 13:46:47,399 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:46:47" (1/1) ... [2024-11-18 13:46:47,399 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:46:47" (1/1) ... [2024-11-18 13:46:47,401 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:46:47" (1/1) ... [2024-11-18 13:46:47,404 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:46:47" (1/1) ... [2024-11-18 13:46:47,404 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:46:47" (1/1) ... [2024-11-18 13:46:47,405 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:46:47" (1/1) ... [2024-11-18 13:46:47,406 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-18 13:46:47,407 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-18 13:46:47,407 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-18 13:46:47,407 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-18 13:46:47,408 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:46:47" (1/1) ... [2024-11-18 13:46:47,413 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-18 13:46:47,421 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:46:47,438 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-18 13:46:47,440 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-18 13:46:47,477 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-18 13:46:47,477 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-18 13:46:47,477 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-11-18 13:46:47,477 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-18 13:46:47,477 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-18 13:46:47,477 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-18 13:46:47,477 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-18 13:46:47,523 INFO L238 CfgBuilder]: Building ICFG [2024-11-18 13:46:47,525 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-18 13:46:47,651 INFO L? ?]: Removed 5 outVars from TransFormulas that were not future-live. [2024-11-18 13:46:47,652 INFO L287 CfgBuilder]: Performing block encoding [2024-11-18 13:46:47,664 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-18 13:46:47,664 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-18 13:46:47,664 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.11 01:46:47 BoogieIcfgContainer [2024-11-18 13:46:47,664 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-18 13:46:47,667 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-18 13:46:47,667 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-18 13:46:47,669 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-18 13:46:47,670 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 18.11 01:46:47" (1/3) ... [2024-11-18 13:46:47,670 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6eaecedf and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.11 01:46:47, skipping insertion in model container [2024-11-18 13:46:47,671 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:46:47" (2/3) ... [2024-11-18 13:46:47,671 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6eaecedf and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.11 01:46:47, skipping insertion in model container [2024-11-18 13:46:47,671 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.11 01:46:47" (3/3) ... [2024-11-18 13:46:47,672 INFO L112 eAbstractionObserver]: Analyzing ICFG hard2_unwindbound50.c [2024-11-18 13:46:47,689 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-18 13:46:47,689 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-18 13:46:47,733 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-18 13:46:47,738 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;@ac851c, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-18 13:46:47,738 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-18 13:46:47,741 INFO L276 IsEmpty]: Start isEmpty. Operand has 26 states, 16 states have (on average 1.5625) internal successors, (25), 17 states have internal predecessors, (25), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-18 13:46:47,746 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2024-11-18 13:46:47,746 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:46:47,747 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:46:47,747 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:46:47,751 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:46:47,751 INFO L85 PathProgramCache]: Analyzing trace with hash 643118537, now seen corresponding path program 1 times [2024-11-18 13:46:47,758 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:46:47,759 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1528624722] [2024-11-18 13:46:47,759 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:46:47,759 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:46:47,849 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:46:47,899 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-18 13:46:47,899 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:46:47,899 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1528624722] [2024-11-18 13:46:47,900 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1528624722] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:46:47,900 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:46:47,900 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-18 13:46:47,902 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [201844598] [2024-11-18 13:46:47,903 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:46:47,907 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-18 13:46:47,908 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:46:47,928 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-18 13:46:47,928 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-18 13:46:47,930 INFO L87 Difference]: Start difference. First operand has 26 states, 16 states have (on average 1.5625) internal successors, (25), 17 states have internal predecessors, (25), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-18 13:46:47,948 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:46:47,949 INFO L93 Difference]: Finished difference Result 50 states and 83 transitions. [2024-11-18 13:46:47,950 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-18 13:46:47,951 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 8 [2024-11-18 13:46:47,951 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:46:47,957 INFO L225 Difference]: With dead ends: 50 [2024-11-18 13:46:47,957 INFO L226 Difference]: Without dead ends: 22 [2024-11-18 13:46:47,960 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-18 13:46:47,964 INFO L432 NwaCegarLoop]: 36 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, 36 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:46:47,965 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:46:47,978 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2024-11-18 13:46:47,993 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 22. [2024-11-18 13:46:47,994 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 22 states, 13 states have (on average 1.4615384615384615) internal successors, (19), 14 states have internal predecessors, (19), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-18 13:46:47,996 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 32 transitions. [2024-11-18 13:46:47,997 INFO L78 Accepts]: Start accepts. Automaton has 22 states and 32 transitions. Word has length 8 [2024-11-18 13:46:47,998 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:46:47,998 INFO L471 AbstractCegarLoop]: Abstraction has 22 states and 32 transitions. [2024-11-18 13:46:47,998 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-18 13:46:47,998 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states and 32 transitions. [2024-11-18 13:46:47,999 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2024-11-18 13:46:47,999 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:46:47,999 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:46:48,000 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-18 13:46:48,000 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:46:48,000 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:46:48,003 INFO L85 PathProgramCache]: Analyzing trace with hash 181060127, now seen corresponding path program 1 times [2024-11-18 13:46:48,003 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:46:48,003 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [443144739] [2024-11-18 13:46:48,003 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:46:48,003 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:46:48,026 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:46:48,166 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-18 13:46:48,166 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:46:48,167 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [443144739] [2024-11-18 13:46:48,167 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [443144739] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:46:48,167 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:46:48,167 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-18 13:46:48,167 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [564995072] [2024-11-18 13:46:48,167 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:46:48,168 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:46:48,168 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:46:48,169 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:46:48,169 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-18 13:46:48,169 INFO L87 Difference]: Start difference. First operand 22 states and 32 transitions. Second operand has 5 states, 5 states have (on average 1.4) internal successors, (7), 4 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-18 13:46:48,230 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:46:48,230 INFO L93 Difference]: Finished difference Result 36 states and 51 transitions. [2024-11-18 13:46:48,231 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-18 13:46:48,231 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.4) internal successors, (7), 4 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 8 [2024-11-18 13:46:48,231 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:46:48,235 INFO L225 Difference]: With dead ends: 36 [2024-11-18 13:46:48,235 INFO L226 Difference]: Without dead ends: 34 [2024-11-18 13:46:48,235 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-18 13:46:48,236 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 12 mSDsluCounter, 69 mSDsCounter, 0 mSdLazyCounter, 21 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 97 SdHoareTripleChecker+Invalid, 21 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 21 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:46:48,237 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 97 Invalid, 21 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 21 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:46:48,239 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2024-11-18 13:46:48,245 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 26. [2024-11-18 13:46:48,246 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 16 states have (on average 1.375) internal successors, (22), 17 states have internal predecessors, (22), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-18 13:46:48,247 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 35 transitions. [2024-11-18 13:46:48,247 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 35 transitions. Word has length 8 [2024-11-18 13:46:48,247 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:46:48,247 INFO L471 AbstractCegarLoop]: Abstraction has 26 states and 35 transitions. [2024-11-18 13:46:48,247 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.4) internal successors, (7), 4 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-18 13:46:48,248 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 35 transitions. [2024-11-18 13:46:48,248 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2024-11-18 13:46:48,248 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:46:48,248 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:46:48,248 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-18 13:46:48,249 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:46:48,249 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:46:48,249 INFO L85 PathProgramCache]: Analyzing trace with hash -712280900, now seen corresponding path program 1 times [2024-11-18 13:46:48,249 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:46:48,250 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2119671098] [2024-11-18 13:46:48,250 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:46:48,250 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:46:48,265 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:46:48,314 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-18 13:46:48,314 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:46:48,314 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2119671098] [2024-11-18 13:46:48,314 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2119671098] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:46:48,315 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:46:48,315 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-18 13:46:48,315 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [117837480] [2024-11-18 13:46:48,315 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:46:48,315 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-18 13:46:48,315 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:46:48,316 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-18 13:46:48,316 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-18 13:46:48,316 INFO L87 Difference]: Start difference. First operand 26 states and 35 transitions. Second operand has 4 states, 4 states have (on average 2.25) internal successors, (9), 3 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-18 13:46:48,334 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:46:48,335 INFO L93 Difference]: Finished difference Result 42 states and 57 transitions. [2024-11-18 13:46:48,335 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-18 13:46:48,335 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.25) internal successors, (9), 3 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 10 [2024-11-18 13:46:48,335 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:46:48,336 INFO L225 Difference]: With dead ends: 42 [2024-11-18 13:46:48,336 INFO L226 Difference]: Without dead ends: 28 [2024-11-18 13:46:48,336 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-18 13:46:48,337 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 0 mSDsluCounter, 55 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 85 SdHoareTripleChecker+Invalid, 9 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:46:48,338 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 85 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:46:48,338 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2024-11-18 13:46:48,342 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 28. [2024-11-18 13:46:48,343 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-18 13:46:48,343 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 37 transitions. [2024-11-18 13:46:48,344 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 37 transitions. Word has length 10 [2024-11-18 13:46:48,344 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:46:48,344 INFO L471 AbstractCegarLoop]: Abstraction has 28 states and 37 transitions. [2024-11-18 13:46:48,344 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.25) internal successors, (9), 3 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-18 13:46:48,344 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 37 transitions. [2024-11-18 13:46:48,345 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2024-11-18 13:46:48,345 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:46:48,345 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:46:48,345 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-11-18 13:46:48,345 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:46:48,345 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:46:48,346 INFO L85 PathProgramCache]: Analyzing trace with hash 2036073049, now seen corresponding path program 1 times [2024-11-18 13:46:48,346 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:46:48,346 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2001677109] [2024-11-18 13:46:48,346 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:46:48,346 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:46:48,358 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:46:48,431 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-18 13:46:48,431 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:46:48,431 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2001677109] [2024-11-18 13:46:48,431 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2001677109] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:46:48,432 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:46:48,432 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-18 13:46:48,432 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1926235367] [2024-11-18 13:46:48,432 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:46:48,432 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:46:48,432 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:46:48,433 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:46:48,433 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-18 13:46:48,433 INFO L87 Difference]: Start difference. First operand 28 states and 37 transitions. Second operand has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-18 13:46:48,486 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:46:48,486 INFO L93 Difference]: Finished difference Result 42 states and 56 transitions. [2024-11-18 13:46:48,487 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-18 13:46:48,487 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 13 [2024-11-18 13:46:48,487 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:46:48,488 INFO L225 Difference]: With dead ends: 42 [2024-11-18 13:46:48,488 INFO L226 Difference]: Without dead ends: 40 [2024-11-18 13:46:48,489 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-18 13:46:48,490 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 12 mSDsluCounter, 66 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 94 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-18 13:46:48,492 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 94 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:46:48,492 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2024-11-18 13:46:48,496 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 32. [2024-11-18 13:46:48,496 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 21 states have (on average 1.2857142857142858) internal successors, (27), 22 states have internal predecessors, (27), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-18 13:46:48,497 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 40 transitions. [2024-11-18 13:46:48,497 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 40 transitions. Word has length 13 [2024-11-18 13:46:48,497 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:46:48,497 INFO L471 AbstractCegarLoop]: Abstraction has 32 states and 40 transitions. [2024-11-18 13:46:48,498 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-18 13:46:48,498 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 40 transitions. [2024-11-18 13:46:48,498 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2024-11-18 13:46:48,498 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:46:48,498 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:46:48,498 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2024-11-18 13:46:48,499 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:46:48,499 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:46:48,499 INFO L85 PathProgramCache]: Analyzing trace with hash 380169759, now seen corresponding path program 1 times [2024-11-18 13:46:48,499 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:46:48,500 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1175707447] [2024-11-18 13:46:48,500 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:46:48,500 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:46:48,512 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:46:48,517 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1557354218] [2024-11-18 13:46:48,517 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:46:48,517 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:46:48,517 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:46:48,519 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:46:48,521 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-18 13:46:48,567 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:46:48,571 INFO L255 TraceCheckSpWp]: Trace formula consists of 83 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-18 13:46:48,575 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:46:48,681 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-18 13:46:48,681 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-18 13:46:48,681 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:46:48,681 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1175707447] [2024-11-18 13:46:48,682 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:46:48,682 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1557354218] [2024-11-18 13:46:48,682 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1557354218] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:46:48,682 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:46:48,682 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-18 13:46:48,682 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [800002920] [2024-11-18 13:46:48,682 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:46:48,682 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:46:48,683 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:46:48,683 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:46:48,683 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-18 13:46:48,683 INFO L87 Difference]: Start difference. First operand 32 states and 40 transitions. Second operand has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-18 13:46:48,730 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:46:48,730 INFO L93 Difference]: Finished difference Result 61 states and 83 transitions. [2024-11-18 13:46:48,731 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-18 13:46:48,731 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2024-11-18 13:46:48,731 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:46:48,731 INFO L225 Difference]: With dead ends: 61 [2024-11-18 13:46:48,731 INFO L226 Difference]: Without dead ends: 46 [2024-11-18 13:46:48,732 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-18 13:46:48,732 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 7 mSDsluCounter, 70 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 98 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 37 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:46:48,732 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 98 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:46:48,733 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2024-11-18 13:46:48,741 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 46. [2024-11-18 13:46:48,741 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 28 states have (on average 1.2857142857142858) internal successors, (36), 30 states have internal predecessors, (36), 13 states have call successors, (13), 4 states have call predecessors, (13), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-18 13:46:48,742 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 60 transitions. [2024-11-18 13:46:48,742 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 60 transitions. Word has length 18 [2024-11-18 13:46:48,742 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:46:48,742 INFO L471 AbstractCegarLoop]: Abstraction has 46 states and 60 transitions. [2024-11-18 13:46:48,742 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-18 13:46:48,742 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 60 transitions. [2024-11-18 13:46:48,743 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2024-11-18 13:46:48,743 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:46:48,743 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:46:48,757 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-18 13:46:48,948 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:46:48,951 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:46:48,951 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:46:48,951 INFO L85 PathProgramCache]: Analyzing trace with hash -461064832, now seen corresponding path program 1 times [2024-11-18 13:46:48,951 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:46:48,951 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [779722567] [2024-11-18 13:46:48,952 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:46:48,952 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:46:48,969 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:46:48,970 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [976262511] [2024-11-18 13:46:48,970 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:46:48,970 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:46:48,971 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:46:48,975 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:46:48,983 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-18 13:46:49,027 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:46:49,028 INFO L255 TraceCheckSpWp]: Trace formula consists of 98 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-11-18 13:46:49,029 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:46:49,108 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 8 proven. 4 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-18 13:46:49,108 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:46:49,260 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 8 proven. 4 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-18 13:46:49,260 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:46:49,260 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [779722567] [2024-11-18 13:46:49,261 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:46:49,261 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [976262511] [2024-11-18 13:46:49,261 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [976262511] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:46:49,261 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:46:49,261 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2024-11-18 13:46:49,261 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [980756192] [2024-11-18 13:46:49,261 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:46:49,262 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-18 13:46:49,262 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:46:49,262 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-18 13:46:49,262 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=67, Unknown=0, NotChecked=0, Total=90 [2024-11-18 13:46:49,262 INFO L87 Difference]: Start difference. First operand 46 states and 60 transitions. Second operand has 10 states, 10 states have (on average 2.3) internal successors, (23), 9 states have internal predecessors, (23), 2 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-18 13:46:49,324 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:46:49,325 INFO L93 Difference]: Finished difference Result 60 states and 79 transitions. [2024-11-18 13:46:49,325 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-18 13:46:49,325 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.3) internal successors, (23), 9 states have internal predecessors, (23), 2 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 26 [2024-11-18 13:46:49,325 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:46:49,326 INFO L225 Difference]: With dead ends: 60 [2024-11-18 13:46:49,326 INFO L226 Difference]: Without dead ends: 57 [2024-11-18 13:46:49,326 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 41 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=31, Invalid=79, Unknown=0, NotChecked=0, Total=110 [2024-11-18 13:46:49,327 INFO L432 NwaCegarLoop]: 19 mSDtfsCounter, 15 mSDsluCounter, 58 mSDsCounter, 0 mSdLazyCounter, 74 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 77 SdHoareTripleChecker+Invalid, 80 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 74 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:46:49,328 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 77 Invalid, 80 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 74 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:46:49,328 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2024-11-18 13:46:49,336 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 56. [2024-11-18 13:46:49,336 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 56 states, 35 states have (on average 1.2857142857142858) internal successors, (45), 37 states have internal predecessors, (45), 15 states have call successors, (15), 5 states have call predecessors, (15), 5 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2024-11-18 13:46:49,337 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 74 transitions. [2024-11-18 13:46:49,337 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 74 transitions. Word has length 26 [2024-11-18 13:46:49,337 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:46:49,337 INFO L471 AbstractCegarLoop]: Abstraction has 56 states and 74 transitions. [2024-11-18 13:46:49,338 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.3) internal successors, (23), 9 states have internal predecessors, (23), 2 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-18 13:46:49,338 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 74 transitions. [2024-11-18 13:46:49,338 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2024-11-18 13:46:49,338 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:46:49,339 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:46:49,351 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-18 13:46:49,539 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,SelfDestructingSolverStorable5 [2024-11-18 13:46:49,540 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:46:49,540 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:46:49,540 INFO L85 PathProgramCache]: Analyzing trace with hash -909290541, now seen corresponding path program 1 times [2024-11-18 13:46:49,540 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:46:49,540 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1110981361] [2024-11-18 13:46:49,540 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:46:49,540 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:46:49,551 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:46:49,629 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-18 13:46:49,629 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:46:49,629 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1110981361] [2024-11-18 13:46:49,629 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1110981361] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:46:49,629 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1561512302] [2024-11-18 13:46:49,629 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:46:49,629 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:46:49,629 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:46:49,631 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:46:49,632 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-18 13:46:49,668 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:46:49,669 INFO L255 TraceCheckSpWp]: Trace formula consists of 116 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-18 13:46:49,670 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:46:49,706 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 18 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2024-11-18 13:46:49,706 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:46:49,750 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-18 13:46:49,750 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1561512302] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:46:49,750 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 13:46:49,750 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 4, 5] total 10 [2024-11-18 13:46:49,750 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [847592668] [2024-11-18 13:46:49,750 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 13:46:49,751 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-18 13:46:49,751 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:46:49,752 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-18 13:46:49,752 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2024-11-18 13:46:49,752 INFO L87 Difference]: Start difference. First operand 56 states and 74 transitions. Second operand has 10 states, 10 states have (on average 3.1) internal successors, (31), 10 states have internal predecessors, (31), 3 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2024-11-18 13:46:49,872 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:46:49,872 INFO L93 Difference]: Finished difference Result 155 states and 190 transitions. [2024-11-18 13:46:49,872 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-18 13:46:49,872 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.1) internal successors, (31), 10 states have internal predecessors, (31), 3 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) Word has length 33 [2024-11-18 13:46:49,872 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:46:49,875 INFO L225 Difference]: With dead ends: 155 [2024-11-18 13:46:49,875 INFO L226 Difference]: Without dead ends: 130 [2024-11-18 13:46:49,875 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 72 GetRequests, 62 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=46, Invalid=86, Unknown=0, NotChecked=0, Total=132 [2024-11-18 13:46:49,876 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 56 mSDsluCounter, 135 mSDsCounter, 0 mSdLazyCounter, 85 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 56 SdHoareTripleChecker+Valid, 166 SdHoareTripleChecker+Invalid, 97 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 85 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:46:49,876 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [56 Valid, 166 Invalid, 97 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 85 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:46:49,877 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2024-11-18 13:46:49,900 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 123. [2024-11-18 13:46:49,900 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 123 states, 79 states have (on average 1.2025316455696202) internal successors, (95), 83 states have internal predecessors, (95), 27 states have call successors, (27), 16 states have call predecessors, (27), 16 states have return successors, (24), 23 states have call predecessors, (24), 24 states have call successors, (24) [2024-11-18 13:46:49,901 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 123 states to 123 states and 146 transitions. [2024-11-18 13:46:49,901 INFO L78 Accepts]: Start accepts. Automaton has 123 states and 146 transitions. Word has length 33 [2024-11-18 13:46:49,902 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:46:49,902 INFO L471 AbstractCegarLoop]: Abstraction has 123 states and 146 transitions. [2024-11-18 13:46:49,902 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.1) internal successors, (31), 10 states have internal predecessors, (31), 3 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2024-11-18 13:46:49,902 INFO L276 IsEmpty]: Start isEmpty. Operand 123 states and 146 transitions. [2024-11-18 13:46:49,903 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2024-11-18 13:46:49,903 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:46:49,903 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1] [2024-11-18 13:46:49,915 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-18 13:46:50,103 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:46:50,104 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:46:50,104 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:46:50,104 INFO L85 PathProgramCache]: Analyzing trace with hash 252591112, now seen corresponding path program 1 times [2024-11-18 13:46:50,104 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:46:50,104 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [35391348] [2024-11-18 13:46:50,104 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:46:50,104 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:46:50,113 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:46:50,114 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [393525536] [2024-11-18 13:46:50,114 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:46:50,114 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:46:50,114 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:46:50,116 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:46:50,116 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-18 13:46:50,153 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:46:50,154 INFO L255 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-18 13:46:50,155 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:46:50,255 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 5 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-18 13:46:50,255 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:46:50,331 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-18 13:46:50,331 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:46:50,332 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [35391348] [2024-11-18 13:46:50,332 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:46:50,332 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [393525536] [2024-11-18 13:46:50,332 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [393525536] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-18 13:46:50,332 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:46:50,332 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2024-11-18 13:46:50,332 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [220663341] [2024-11-18 13:46:50,332 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:46:50,333 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:46:50,333 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:46:50,333 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:46:50,333 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-18 13:46:50,333 INFO L87 Difference]: Start difference. First operand 123 states and 146 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-18 13:46:51,830 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.45s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-18 13:46:51,848 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:46:51,850 INFO L93 Difference]: Finished difference Result 146 states and 174 transitions. [2024-11-18 13:46:51,850 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-18 13:46:51,851 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 36 [2024-11-18 13:46:51,851 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:46:51,852 INFO L225 Difference]: With dead ends: 146 [2024-11-18 13:46:51,852 INFO L226 Difference]: Without dead ends: 140 [2024-11-18 13:46:51,852 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 71 GetRequests, 63 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-18 13:46:51,853 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 8 mSDsluCounter, 64 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 92 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.5s IncrementalHoareTripleChecker+Time [2024-11-18 13:46:51,853 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 92 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 1.5s Time] [2024-11-18 13:46:51,854 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 140 states. [2024-11-18 13:46:51,874 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 140 to 132. [2024-11-18 13:46:51,874 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 132 states, 86 states have (on average 1.1744186046511629) internal successors, (101), 90 states have internal predecessors, (101), 28 states have call successors, (28), 18 states have call predecessors, (28), 17 states have return successors, (26), 23 states have call predecessors, (26), 26 states have call successors, (26) [2024-11-18 13:46:51,875 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 132 states to 132 states and 155 transitions. [2024-11-18 13:46:51,876 INFO L78 Accepts]: Start accepts. Automaton has 132 states and 155 transitions. Word has length 36 [2024-11-18 13:46:51,876 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:46:51,876 INFO L471 AbstractCegarLoop]: Abstraction has 132 states and 155 transitions. [2024-11-18 13:46:51,876 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-18 13:46:51,876 INFO L276 IsEmpty]: Start isEmpty. Operand 132 states and 155 transitions. [2024-11-18 13:46:51,877 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2024-11-18 13:46:51,877 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:46:51,877 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 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-18 13:46:51,889 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-18 13:46:52,081 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:46:52,082 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:46:52,082 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:46:52,082 INFO L85 PathProgramCache]: Analyzing trace with hash 1776130969, now seen corresponding path program 1 times [2024-11-18 13:46:52,082 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:46:52,082 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [757927678] [2024-11-18 13:46:52,082 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:46:52,082 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:46:52,090 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:46:52,174 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-11-18 13:46:52,174 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:46:52,174 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [757927678] [2024-11-18 13:46:52,174 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [757927678] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:46:52,174 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:46:52,174 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-18 13:46:52,174 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [929520637] [2024-11-18 13:46:52,175 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:46:52,175 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:46:52,175 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:46:52,175 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:46:52,175 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-18 13:46:52,176 INFO L87 Difference]: Start difference. First operand 132 states and 155 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 1 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2024-11-18 13:46:52,211 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:46:52,213 INFO L93 Difference]: Finished difference Result 137 states and 159 transitions. [2024-11-18 13:46:52,213 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-18 13:46:52,213 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 1 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) Word has length 42 [2024-11-18 13:46:52,214 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:46:52,215 INFO L225 Difference]: With dead ends: 137 [2024-11-18 13:46:52,215 INFO L226 Difference]: Without dead ends: 118 [2024-11-18 13:46:52,215 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-18 13:46:52,216 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 1 mSDsluCounter, 79 mSDsCounter, 0 mSdLazyCounter, 24 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 111 SdHoareTripleChecker+Invalid, 24 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 24 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:46:52,217 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 111 Invalid, 24 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:46:52,217 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 118 states. [2024-11-18 13:46:52,235 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 118 to 118. [2024-11-18 13:46:52,236 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 118 states, 77 states have (on average 1.1818181818181819) internal successors, (91), 80 states have internal predecessors, (91), 25 states have call successors, (25), 16 states have call predecessors, (25), 15 states have return successors, (23), 21 states have call predecessors, (23), 23 states have call successors, (23) [2024-11-18 13:46:52,238 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 139 transitions. [2024-11-18 13:46:52,238 INFO L78 Accepts]: Start accepts. Automaton has 118 states and 139 transitions. Word has length 42 [2024-11-18 13:46:52,238 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:46:52,238 INFO L471 AbstractCegarLoop]: Abstraction has 118 states and 139 transitions. [2024-11-18 13:46:52,238 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 1 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2024-11-18 13:46:52,240 INFO L276 IsEmpty]: Start isEmpty. Operand 118 states and 139 transitions. [2024-11-18 13:46:52,241 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2024-11-18 13:46:52,241 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:46:52,241 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:46:52,241 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8 [2024-11-18 13:46:52,242 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:46:52,242 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:46:52,242 INFO L85 PathProgramCache]: Analyzing trace with hash 1605675221, now seen corresponding path program 1 times [2024-11-18 13:46:52,242 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:46:52,242 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2098822188] [2024-11-18 13:46:52,242 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:46:52,242 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:46:52,256 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:46:52,329 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 14 proven. 6 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2024-11-18 13:46:52,329 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:46:52,330 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2098822188] [2024-11-18 13:46:52,330 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2098822188] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:46:52,330 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [149409996] [2024-11-18 13:46:52,330 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:46:52,330 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:46:52,330 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:46:52,334 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:46:52,337 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-18 13:46:52,377 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:46:52,377 INFO L255 TraceCheckSpWp]: Trace formula consists of 144 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-18 13:46:52,379 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:46:52,445 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 36 proven. 42 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2024-11-18 13:46:52,445 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:46:52,514 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 14 proven. 6 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2024-11-18 13:46:52,515 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [149409996] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:46:52,515 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 13:46:52,515 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 5, 6] total 12 [2024-11-18 13:46:52,515 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [535023647] [2024-11-18 13:46:52,515 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 13:46:52,516 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-18 13:46:52,516 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:46:52,516 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-18 13:46:52,516 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=84, Unknown=0, NotChecked=0, Total=132 [2024-11-18 13:46:52,517 INFO L87 Difference]: Start difference. First operand 118 states and 139 transitions. Second operand has 12 states, 12 states have (on average 3.1666666666666665) internal successors, (38), 12 states have internal predecessors, (38), 5 states have call successors, (21), 4 states have call predecessors, (21), 4 states have return successors, (20), 5 states have call predecessors, (20), 5 states have call successors, (20) [2024-11-18 13:46:52,680 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:46:52,680 INFO L93 Difference]: Finished difference Result 241 states and 294 transitions. [2024-11-18 13:46:52,684 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-18 13:46:52,684 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 3.1666666666666665) internal successors, (38), 12 states have internal predecessors, (38), 5 states have call successors, (21), 4 states have call predecessors, (21), 4 states have return successors, (20), 5 states have call predecessors, (20), 5 states have call successors, (20) Word has length 49 [2024-11-18 13:46:52,684 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:46:52,686 INFO L225 Difference]: With dead ends: 241 [2024-11-18 13:46:52,686 INFO L226 Difference]: Without dead ends: 220 [2024-11-18 13:46:52,686 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 106 GetRequests, 93 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 25 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=67, Invalid=143, Unknown=0, NotChecked=0, Total=210 [2024-11-18 13:46:52,687 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 79 mSDsluCounter, 154 mSDsCounter, 0 mSdLazyCounter, 110 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 79 SdHoareTripleChecker+Valid, 184 SdHoareTripleChecker+Invalid, 125 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 110 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:46:52,687 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [79 Valid, 184 Invalid, 125 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 110 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:46:52,689 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 220 states. [2024-11-18 13:46:52,708 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 220 to 213. [2024-11-18 13:46:52,709 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 213 states, 138 states have (on average 1.1956521739130435) internal successors, (165), 147 states have internal predecessors, (165), 49 states have call successors, (49), 26 states have call predecessors, (49), 25 states have return successors, (45), 39 states have call predecessors, (45), 45 states have call successors, (45) [2024-11-18 13:46:52,710 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 213 states to 213 states and 259 transitions. [2024-11-18 13:46:52,710 INFO L78 Accepts]: Start accepts. Automaton has 213 states and 259 transitions. Word has length 49 [2024-11-18 13:46:52,711 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:46:52,711 INFO L471 AbstractCegarLoop]: Abstraction has 213 states and 259 transitions. [2024-11-18 13:46:52,713 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 3.1666666666666665) internal successors, (38), 12 states have internal predecessors, (38), 5 states have call successors, (21), 4 states have call predecessors, (21), 4 states have return successors, (20), 5 states have call predecessors, (20), 5 states have call successors, (20) [2024-11-18 13:46:52,713 INFO L276 IsEmpty]: Start isEmpty. Operand 213 states and 259 transitions. [2024-11-18 13:46:52,714 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2024-11-18 13:46:52,716 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:46:52,716 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:46:52,734 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-18 13:46:52,917 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-11-18 13:46:52,917 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:46:52,918 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:46:52,918 INFO L85 PathProgramCache]: Analyzing trace with hash -1800695307, now seen corresponding path program 1 times [2024-11-18 13:46:52,918 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:46:52,918 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1101324383] [2024-11-18 13:46:52,918 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:46:52,918 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:46:52,936 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:46:52,937 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [871348789] [2024-11-18 13:46:52,937 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:46:52,937 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:46:52,937 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:46:52,939 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:46:52,940 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-18 13:46:52,994 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:46:52,995 INFO L255 TraceCheckSpWp]: Trace formula consists of 168 conjuncts, 33 conjuncts are in the unsatisfiable core [2024-11-18 13:46:52,998 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:46:53,227 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 18 proven. 28 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2024-11-18 13:46:53,227 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:46:54,408 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 18 proven. 28 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2024-11-18 13:46:54,409 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:46:54,409 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1101324383] [2024-11-18 13:46:54,409 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:46:54,409 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [871348789] [2024-11-18 13:46:54,409 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [871348789] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:46:54,409 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:46:54,409 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2024-11-18 13:46:54,409 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1481153139] [2024-11-18 13:46:54,409 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:46:54,410 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-18 13:46:54,410 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:46:54,410 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-18 13:46:54,410 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=43, Invalid=167, Unknown=0, NotChecked=0, Total=210 [2024-11-18 13:46:54,411 INFO L87 Difference]: Start difference. First operand 213 states and 259 transitions. Second operand has 15 states, 15 states have (on average 2.6666666666666665) internal successors, (40), 14 states have internal predecessors, (40), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) [2024-11-18 13:46:54,977 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:46:54,977 INFO L93 Difference]: Finished difference Result 359 states and 460 transitions. [2024-11-18 13:46:54,977 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-18 13:46:54,977 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.6666666666666665) internal successors, (40), 14 states have internal predecessors, (40), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) Word has length 58 [2024-11-18 13:46:54,978 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:46:54,980 INFO L225 Difference]: With dead ends: 359 [2024-11-18 13:46:54,980 INFO L226 Difference]: Without dead ends: 298 [2024-11-18 13:46:54,980 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 118 GetRequests, 101 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=76, Invalid=266, Unknown=0, NotChecked=0, Total=342 [2024-11-18 13:46:54,981 INFO L432 NwaCegarLoop]: 40 mSDtfsCounter, 44 mSDsluCounter, 248 mSDsCounter, 0 mSdLazyCounter, 269 mSolverCounterSat, 58 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 50 SdHoareTripleChecker+Valid, 288 SdHoareTripleChecker+Invalid, 327 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 58 IncrementalHoareTripleChecker+Valid, 269 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-18 13:46:54,981 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [50 Valid, 288 Invalid, 327 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [58 Valid, 269 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-18 13:46:54,984 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 298 states. [2024-11-18 13:46:55,021 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 298 to 272. [2024-11-18 13:46:55,022 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 272 states, 185 states have (on average 1.227027027027027) internal successors, (227), 192 states have internal predecessors, (227), 57 states have call successors, (57), 29 states have call predecessors, (57), 29 states have return successors, (55), 50 states have call predecessors, (55), 55 states have call successors, (55) [2024-11-18 13:46:55,024 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 272 states to 272 states and 339 transitions. [2024-11-18 13:46:55,025 INFO L78 Accepts]: Start accepts. Automaton has 272 states and 339 transitions. Word has length 58 [2024-11-18 13:46:55,026 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:46:55,026 INFO L471 AbstractCegarLoop]: Abstraction has 272 states and 339 transitions. [2024-11-18 13:46:55,026 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.6666666666666665) internal successors, (40), 14 states have internal predecessors, (40), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) [2024-11-18 13:46:55,026 INFO L276 IsEmpty]: Start isEmpty. Operand 272 states and 339 transitions. [2024-11-18 13:46:55,027 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2024-11-18 13:46:55,030 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:46:55,030 INFO L215 NwaCegarLoop]: trace histogram [11, 10, 10, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:46:55,047 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-18 13:46:55,230 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:46:55,231 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:46:55,231 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:46:55,231 INFO L85 PathProgramCache]: Analyzing trace with hash -1688778742, now seen corresponding path program 1 times [2024-11-18 13:46:55,231 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:46:55,232 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1045554193] [2024-11-18 13:46:55,232 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:46:55,232 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:46:55,246 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:46:55,247 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [486570765] [2024-11-18 13:46:55,247 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:46:55,247 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:46:55,247 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:46:55,249 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:46:55,250 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-18 13:46:55,291 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:46:55,292 INFO L255 TraceCheckSpWp]: Trace formula consists of 188 conjuncts, 35 conjuncts are in the unsatisfiable core [2024-11-18 13:46:55,294 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:46:55,487 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 22 proven. 36 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2024-11-18 13:46:55,487 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:46:55,887 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 22 proven. 36 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2024-11-18 13:46:55,887 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:46:55,887 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1045554193] [2024-11-18 13:46:55,888 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:46:55,888 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [486570765] [2024-11-18 13:46:55,888 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [486570765] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:46:55,888 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:46:55,888 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9] total 16 [2024-11-18 13:46:55,888 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [490525966] [2024-11-18 13:46:55,888 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:46:55,889 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-18 13:46:55,889 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:46:55,889 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-18 13:46:55,889 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=187, Unknown=0, NotChecked=0, Total=240 [2024-11-18 13:46:55,890 INFO L87 Difference]: Start difference. First operand 272 states and 339 transitions. Second operand has 16 states, 14 states have (on average 3.0) internal successors, (42), 15 states have internal predecessors, (42), 8 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 6 states have call predecessors, (20), 6 states have call successors, (20) [2024-11-18 13:46:56,325 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:46:56,326 INFO L93 Difference]: Finished difference Result 337 states and 420 transitions. [2024-11-18 13:46:56,326 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-18 13:46:56,326 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 14 states have (on average 3.0) internal successors, (42), 15 states have internal predecessors, (42), 8 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 6 states have call predecessors, (20), 6 states have call successors, (20) Word has length 69 [2024-11-18 13:46:56,326 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:46:56,328 INFO L225 Difference]: With dead ends: 337 [2024-11-18 13:46:56,328 INFO L226 Difference]: Without dead ends: 269 [2024-11-18 13:46:56,328 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 139 GetRequests, 122 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=79, Invalid=263, Unknown=0, NotChecked=0, Total=342 [2024-11-18 13:46:56,329 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 23 mSDsluCounter, 240 mSDsCounter, 0 mSdLazyCounter, 296 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 275 SdHoareTripleChecker+Invalid, 322 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 296 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-18 13:46:56,329 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 275 Invalid, 322 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 296 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-18 13:46:56,333 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 269 states. [2024-11-18 13:46:56,370 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 269 to 243. [2024-11-18 13:46:56,370 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 243 states, 166 states have (on average 1.180722891566265) internal successors, (196), 171 states have internal predecessors, (196), 47 states have call successors, (47), 30 states have call predecessors, (47), 29 states have return successors, (45), 41 states have call predecessors, (45), 45 states have call successors, (45) [2024-11-18 13:46:56,372 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 243 states to 243 states and 288 transitions. [2024-11-18 13:46:56,372 INFO L78 Accepts]: Start accepts. Automaton has 243 states and 288 transitions. Word has length 69 [2024-11-18 13:46:56,372 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:46:56,372 INFO L471 AbstractCegarLoop]: Abstraction has 243 states and 288 transitions. [2024-11-18 13:46:56,373 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 14 states have (on average 3.0) internal successors, (42), 15 states have internal predecessors, (42), 8 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 6 states have call predecessors, (20), 6 states have call successors, (20) [2024-11-18 13:46:56,373 INFO L276 IsEmpty]: Start isEmpty. Operand 243 states and 288 transitions. [2024-11-18 13:46:56,374 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2024-11-18 13:46:56,374 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:46:56,374 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:46:56,390 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-18 13:46:56,578 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:46:56,579 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:46:56,579 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:46:56,579 INFO L85 PathProgramCache]: Analyzing trace with hash -428937714, now seen corresponding path program 1 times [2024-11-18 13:46:56,579 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:46:56,579 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1202987475] [2024-11-18 13:46:56,579 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:46:56,579 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:46:56,595 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:46:56,825 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 22 proven. 11 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2024-11-18 13:46:56,825 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:46:56,825 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1202987475] [2024-11-18 13:46:56,825 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1202987475] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:46:56,825 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [602889046] [2024-11-18 13:46:56,825 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:46:56,825 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:46:56,826 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:46:56,827 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:46:56,828 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-18 13:46:56,868 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:46:56,869 INFO L255 TraceCheckSpWp]: Trace formula consists of 197 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-11-18 13:46:56,870 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:46:56,998 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 22 proven. 11 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2024-11-18 13:46:56,998 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:46:57,314 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 22 proven. 11 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2024-11-18 13:46:57,314 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [602889046] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:46:57,314 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 13:46:57,314 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7, 7] total 14 [2024-11-18 13:46:57,315 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [922073320] [2024-11-18 13:46:57,315 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 13:46:57,315 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-18 13:46:57,315 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:46:57,316 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-18 13:46:57,316 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=144, Unknown=0, NotChecked=0, Total=182 [2024-11-18 13:46:57,316 INFO L87 Difference]: Start difference. First operand 243 states and 288 transitions. Second operand has 14 states, 14 states have (on average 3.642857142857143) internal successors, (51), 12 states have internal predecessors, (51), 8 states have call successors, (35), 3 states have call predecessors, (35), 1 states have return successors, (32), 8 states have call predecessors, (32), 8 states have call successors, (32) [2024-11-18 13:46:57,545 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:46:57,545 INFO L93 Difference]: Finished difference Result 281 states and 329 transitions. [2024-11-18 13:46:57,545 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-18 13:46:57,546 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 3.642857142857143) internal successors, (51), 12 states have internal predecessors, (51), 8 states have call successors, (35), 3 states have call predecessors, (35), 1 states have return successors, (32), 8 states have call predecessors, (32), 8 states have call successors, (32) Word has length 74 [2024-11-18 13:46:57,546 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:46:57,547 INFO L225 Difference]: With dead ends: 281 [2024-11-18 13:46:57,547 INFO L226 Difference]: Without dead ends: 215 [2024-11-18 13:46:57,548 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 158 GetRequests, 140 SyntacticMatches, 2 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 51 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=67, Invalid=239, Unknown=0, NotChecked=0, Total=306 [2024-11-18 13:46:57,548 INFO L432 NwaCegarLoop]: 41 mSDtfsCounter, 15 mSDsluCounter, 293 mSDsCounter, 0 mSdLazyCounter, 161 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 334 SdHoareTripleChecker+Invalid, 176 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 161 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:46:57,548 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 334 Invalid, 176 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 161 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:46:57,548 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 215 states. [2024-11-18 13:46:57,601 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 215 to 210. [2024-11-18 13:46:57,602 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 210 states, 144 states have (on average 1.1527777777777777) internal successors, (166), 147 states have internal predecessors, (166), 40 states have call successors, (40), 25 states have call predecessors, (40), 25 states have return successors, (39), 37 states have call predecessors, (39), 39 states have call successors, (39) [2024-11-18 13:46:57,603 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 210 states to 210 states and 245 transitions. [2024-11-18 13:46:57,603 INFO L78 Accepts]: Start accepts. Automaton has 210 states and 245 transitions. Word has length 74 [2024-11-18 13:46:57,603 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:46:57,603 INFO L471 AbstractCegarLoop]: Abstraction has 210 states and 245 transitions. [2024-11-18 13:46:57,603 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 3.642857142857143) internal successors, (51), 12 states have internal predecessors, (51), 8 states have call successors, (35), 3 states have call predecessors, (35), 1 states have return successors, (32), 8 states have call predecessors, (32), 8 states have call successors, (32) [2024-11-18 13:46:57,604 INFO L276 IsEmpty]: Start isEmpty. Operand 210 states and 245 transitions. [2024-11-18 13:46:57,604 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2024-11-18 13:46:57,604 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:46:57,604 INFO L215 NwaCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2024-11-18 13:46:57,618 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2024-11-18 13:46:57,805 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,SelfDestructingSolverStorable12 [2024-11-18 13:46:57,806 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:46:57,806 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:46:57,806 INFO L85 PathProgramCache]: Analyzing trace with hash 1611798954, now seen corresponding path program 2 times [2024-11-18 13:46:57,806 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:46:57,807 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [398814809] [2024-11-18 13:46:57,807 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:46:57,807 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:46:57,840 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:46:57,841 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:46:57,844 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1198846804] [2024-11-18 13:46:57,844 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:46:57,844 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:46:57,845 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:46:57,846 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:46:57,847 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-18 13:46:57,897 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:46:57,897 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:46:57,898 INFO L255 TraceCheckSpWp]: Trace formula consists of 238 conjuncts, 48 conjuncts are in the unsatisfiable core [2024-11-18 13:46:57,900 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:46:58,272 INFO L134 CoverageAnalysis]: Checked inductivity of 368 backedges. 28 proven. 64 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2024-11-18 13:46:58,273 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:47:15,648 INFO L134 CoverageAnalysis]: Checked inductivity of 368 backedges. 28 proven. 64 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2024-11-18 13:47:15,648 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:47:15,648 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [398814809] [2024-11-18 13:47:15,648 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:47:15,648 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1198846804] [2024-11-18 13:47:15,648 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1198846804] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:47:15,649 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:47:15,649 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 25 [2024-11-18 13:47:15,649 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1572661036] [2024-11-18 13:47:15,649 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:47:15,649 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2024-11-18 13:47:15,649 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:47:15,650 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2024-11-18 13:47:15,650 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=107, Invalid=493, Unknown=0, NotChecked=0, Total=600 [2024-11-18 13:47:15,650 INFO L87 Difference]: Start difference. First operand 210 states and 245 transitions. Second operand has 25 states, 25 states have (on average 2.16) internal successors, (54), 23 states have internal predecessors, (54), 13 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 11 states have call predecessors, (26), 11 states have call successors, (26) [2024-11-18 13:47:27,678 WARN L286 SmtUtils]: Spent 8.81s on a formula simplification. DAG size of input: 223 DAG size of output: 125 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-18 13:47:28,429 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:47:28,430 INFO L93 Difference]: Finished difference Result 319 states and 404 transitions. [2024-11-18 13:47:28,430 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2024-11-18 13:47:28,430 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 25 states have (on average 2.16) internal successors, (54), 23 states have internal predecessors, (54), 13 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 11 states have call predecessors, (26), 11 states have call successors, (26) Word has length 90 [2024-11-18 13:47:28,430 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:47:28,432 INFO L225 Difference]: With dead ends: 319 [2024-11-18 13:47:28,432 INFO L226 Difference]: Without dead ends: 283 [2024-11-18 13:47:28,432 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 195 GetRequests, 155 SyntacticMatches, 0 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 240 ImplicationChecksByTransitivity, 14.4s TimeCoverageRelationStatistics Valid=359, Invalid=1363, Unknown=0, NotChecked=0, Total=1722 [2024-11-18 13:47:28,433 INFO L432 NwaCegarLoop]: 57 mSDtfsCounter, 77 mSDsluCounter, 522 mSDsCounter, 0 mSdLazyCounter, 630 mSolverCounterSat, 147 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 79 SdHoareTripleChecker+Valid, 579 SdHoareTripleChecker+Invalid, 777 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 147 IncrementalHoareTripleChecker+Valid, 630 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.6s IncrementalHoareTripleChecker+Time [2024-11-18 13:47:28,433 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [79 Valid, 579 Invalid, 777 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [147 Valid, 630 Invalid, 0 Unknown, 0 Unchecked, 1.6s Time] [2024-11-18 13:47:28,434 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 283 states. [2024-11-18 13:47:28,481 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 283 to 245. [2024-11-18 13:47:28,482 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 245 states, 167 states have (on average 1.1736526946107784) internal successors, (196), 171 states have internal predecessors, (196), 49 states have call successors, (49), 28 states have call predecessors, (49), 28 states have return successors, (48), 45 states have call predecessors, (48), 48 states have call successors, (48) [2024-11-18 13:47:28,483 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 245 states to 245 states and 293 transitions. [2024-11-18 13:47:28,484 INFO L78 Accepts]: Start accepts. Automaton has 245 states and 293 transitions. Word has length 90 [2024-11-18 13:47:28,485 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:47:28,485 INFO L471 AbstractCegarLoop]: Abstraction has 245 states and 293 transitions. [2024-11-18 13:47:28,485 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 25 states have (on average 2.16) internal successors, (54), 23 states have internal predecessors, (54), 13 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 11 states have call predecessors, (26), 11 states have call successors, (26) [2024-11-18 13:47:28,485 INFO L276 IsEmpty]: Start isEmpty. Operand 245 states and 293 transitions. [2024-11-18 13:47:28,486 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 96 [2024-11-18 13:47:28,486 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:47:28,486 INFO L215 NwaCegarLoop]: trace histogram [15, 14, 14, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2024-11-18 13:47:28,499 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2024-11-18 13:47:28,690 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,SelfDestructingSolverStorable13 [2024-11-18 13:47:28,691 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:47:28,691 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:47:28,691 INFO L85 PathProgramCache]: Analyzing trace with hash -1147408146, now seen corresponding path program 3 times [2024-11-18 13:47:28,691 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:47:28,691 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1948198944] [2024-11-18 13:47:28,691 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-18 13:47:28,691 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:47:28,723 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 9 check-sat command(s) [2024-11-18 13:47:28,724 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:47:28,726 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [335287142] [2024-11-18 13:47:28,726 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-18 13:47:28,727 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:47:28,727 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:47:28,728 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:47:28,730 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-18 13:47:28,777 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2024-11-18 13:47:28,777 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:47:28,778 INFO L255 TraceCheckSpWp]: Trace formula consists of 172 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-11-18 13:47:28,780 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:47:28,897 INFO L134 CoverageAnalysis]: Checked inductivity of 424 backedges. 81 proven. 41 refuted. 0 times theorem prover too weak. 302 trivial. 0 not checked. [2024-11-18 13:47:28,897 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:47:29,770 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:47:29,771 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1948198944] [2024-11-18 13:47:29,771 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:47:29,771 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [335287142] [2024-11-18 13:47:29,771 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [335287142] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:47:29,771 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:47:29,771 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2024-11-18 13:47:29,771 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1449014226] [2024-11-18 13:47:29,771 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-18 13:47:29,771 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-18 13:47:29,771 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:47:29,772 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-18 13:47:29,772 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=32, Invalid=124, Unknown=0, NotChecked=0, Total=156 [2024-11-18 13:47:29,772 INFO L87 Difference]: Start difference. First operand 245 states and 293 transitions. Second operand has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2024-11-18 13:47:29,928 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:47:29,929 INFO L93 Difference]: Finished difference Result 268 states and 314 transitions. [2024-11-18 13:47:29,929 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-18 13:47:29,929 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) Word has length 95 [2024-11-18 13:47:29,929 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:47:29,931 INFO L225 Difference]: With dead ends: 268 [2024-11-18 13:47:29,931 INFO L226 Difference]: Without dead ends: 266 [2024-11-18 13:47:29,931 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 110 GetRequests, 97 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=47, Invalid=163, Unknown=0, NotChecked=0, Total=210 [2024-11-18 13:47:29,932 INFO L432 NwaCegarLoop]: 22 mSDtfsCounter, 19 mSDsluCounter, 85 mSDsCounter, 0 mSdLazyCounter, 126 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 107 SdHoareTripleChecker+Invalid, 136 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 126 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:47:29,932 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 107 Invalid, 136 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 126 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:47:29,932 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 266 states. [2024-11-18 13:47:29,988 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 266 to 261. [2024-11-18 13:47:29,988 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 261 states, 179 states have (on average 1.1620111731843576) internal successors, (208), 183 states have internal predecessors, (208), 49 states have call successors, (49), 32 states have call predecessors, (49), 32 states have return successors, (48), 45 states have call predecessors, (48), 48 states have call successors, (48) [2024-11-18 13:47:29,989 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 261 states to 261 states and 305 transitions. [2024-11-18 13:47:29,990 INFO L78 Accepts]: Start accepts. Automaton has 261 states and 305 transitions. Word has length 95 [2024-11-18 13:47:29,990 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:47:29,990 INFO L471 AbstractCegarLoop]: Abstraction has 261 states and 305 transitions. [2024-11-18 13:47:29,990 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2024-11-18 13:47:29,990 INFO L276 IsEmpty]: Start isEmpty. Operand 261 states and 305 transitions. [2024-11-18 13:47:29,991 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2024-11-18 13:47:29,991 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:47:29,991 INFO L215 NwaCegarLoop]: trace histogram [15, 14, 14, 5, 4, 4, 4, 4, 4, 4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:47:30,004 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2024-11-18 13:47:30,193 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,SelfDestructingSolverStorable14 [2024-11-18 13:47:30,194 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:47:30,194 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:47:30,194 INFO L85 PathProgramCache]: Analyzing trace with hash 1991126182, now seen corresponding path program 1 times [2024-11-18 13:47:30,194 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:47:30,194 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1314443624] [2024-11-18 13:47:30,194 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:47:30,194 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:47:30,202 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:47:30,329 INFO L134 CoverageAnalysis]: Checked inductivity of 438 backedges. 28 proven. 44 refuted. 0 times theorem prover too weak. 366 trivial. 0 not checked. [2024-11-18 13:47:30,330 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:47:30,330 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1314443624] [2024-11-18 13:47:30,330 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1314443624] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:47:30,330 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2125551686] [2024-11-18 13:47:30,330 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:47:30,330 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:47:30,330 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:47:30,333 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-18 13:47:30,337 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-18 13:47:30,391 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:47:30,393 INFO L255 TraceCheckSpWp]: Trace formula consists of 251 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-18 13:47:30,394 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:47:30,481 INFO L134 CoverageAnalysis]: Checked inductivity of 438 backedges. 120 proven. 260 refuted. 0 times theorem prover too weak. 58 trivial. 0 not checked. [2024-11-18 13:47:30,481 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:47:30,599 INFO L134 CoverageAnalysis]: Checked inductivity of 438 backedges. 28 proven. 44 refuted. 0 times theorem prover too weak. 366 trivial. 0 not checked. [2024-11-18 13:47:30,600 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2125551686] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:47:30,600 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 13:47:30,600 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7, 8] total 16 [2024-11-18 13:47:30,600 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1282563275] [2024-11-18 13:47:30,600 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 13:47:30,600 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-18 13:47:30,601 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:47:30,601 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-18 13:47:30,601 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=96, Invalid=144, Unknown=0, NotChecked=0, Total=240 [2024-11-18 13:47:30,601 INFO L87 Difference]: Start difference. First operand 261 states and 305 transitions. Second operand has 16 states, 16 states have (on average 3.8125) internal successors, (61), 16 states have internal predecessors, (61), 9 states have call successors, (41), 6 states have call predecessors, (41), 6 states have return successors, (40), 9 states have call predecessors, (40), 9 states have call successors, (40) [2024-11-18 13:47:30,947 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:47:30,948 INFO L93 Difference]: Finished difference Result 720 states and 884 transitions. [2024-11-18 13:47:30,948 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-11-18 13:47:30,948 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 3.8125) internal successors, (61), 16 states have internal predecessors, (61), 9 states have call successors, (41), 6 states have call predecessors, (41), 6 states have return successors, (40), 9 states have call predecessors, (40), 9 states have call successors, (40) Word has length 96 [2024-11-18 13:47:30,949 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:47:30,951 INFO L225 Difference]: With dead ends: 720 [2024-11-18 13:47:30,951 INFO L226 Difference]: Without dead ends: 650 [2024-11-18 13:47:30,952 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 207 GetRequests, 185 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 75 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=196, Invalid=356, Unknown=0, NotChecked=0, Total=552 [2024-11-18 13:47:30,952 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 118 mSDsluCounter, 160 mSDsCounter, 0 mSdLazyCounter, 149 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 118 SdHoareTripleChecker+Valid, 189 SdHoareTripleChecker+Invalid, 156 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 149 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:47:30,952 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [118 Valid, 189 Invalid, 156 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 149 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:47:30,953 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 650 states. [2024-11-18 13:47:31,099 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 650 to 562. [2024-11-18 13:47:31,100 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 562 states, 376 states have (on average 1.2074468085106382) internal successors, (454), 394 states have internal predecessors, (454), 116 states have call successors, (116), 69 states have call predecessors, (116), 69 states have return successors, (112), 98 states have call predecessors, (112), 112 states have call successors, (112) [2024-11-18 13:47:31,102 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 562 states to 562 states and 682 transitions. [2024-11-18 13:47:31,102 INFO L78 Accepts]: Start accepts. Automaton has 562 states and 682 transitions. Word has length 96 [2024-11-18 13:47:31,103 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:47:31,103 INFO L471 AbstractCegarLoop]: Abstraction has 562 states and 682 transitions. [2024-11-18 13:47:31,103 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 3.8125) internal successors, (61), 16 states have internal predecessors, (61), 9 states have call successors, (41), 6 states have call predecessors, (41), 6 states have return successors, (40), 9 states have call predecessors, (40), 9 states have call successors, (40) [2024-11-18 13:47:31,103 INFO L276 IsEmpty]: Start isEmpty. Operand 562 states and 682 transitions. [2024-11-18 13:47:31,104 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2024-11-18 13:47:31,104 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:47:31,104 INFO L215 NwaCegarLoop]: trace histogram [16, 15, 15, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:47:31,117 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-18 13:47:31,308 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,SelfDestructingSolverStorable15 [2024-11-18 13:47:31,309 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:47:31,309 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:47:31,309 INFO L85 PathProgramCache]: Analyzing trace with hash -218084043, now seen corresponding path program 2 times [2024-11-18 13:47:31,309 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:47:31,309 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1280563168] [2024-11-18 13:47:31,309 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:47:31,309 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:47:31,335 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:47:31,335 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:47:31,336 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1598670245] [2024-11-18 13:47:31,336 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:47:31,336 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:47:31,336 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:47:31,341 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-18 13:47:31,342 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-18 13:47:31,397 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:47:31,397 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:47:31,398 INFO L255 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 54 conjuncts are in the unsatisfiable core [2024-11-18 13:47:31,400 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:47:31,755 INFO L134 CoverageAnalysis]: Checked inductivity of 484 backedges. 32 proven. 74 refuted. 0 times theorem prover too weak. 378 trivial. 0 not checked. [2024-11-18 13:47:31,756 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:47:33,825 INFO L134 CoverageAnalysis]: Checked inductivity of 484 backedges. 32 proven. 74 refuted. 0 times theorem prover too weak. 378 trivial. 0 not checked. [2024-11-18 13:47:33,825 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:47:33,825 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1280563168] [2024-11-18 13:47:33,825 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:47:33,825 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1598670245] [2024-11-18 13:47:33,826 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1598670245] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:47:33,826 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:47:33,826 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15] total 27 [2024-11-18 13:47:33,826 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1303778158] [2024-11-18 13:47:33,826 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:47:33,826 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2024-11-18 13:47:33,826 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:47:33,827 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2024-11-18 13:47:33,827 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=157, Invalid=545, Unknown=0, NotChecked=0, Total=702 [2024-11-18 13:47:33,827 INFO L87 Difference]: Start difference. First operand 562 states and 682 transitions. Second operand has 27 states, 25 states have (on average 2.24) internal successors, (56), 25 states have internal predecessors, (56), 15 states have call successors, (32), 3 states have call predecessors, (32), 2 states have return successors, (30), 13 states have call predecessors, (30), 13 states have call successors, (30) [2024-11-18 13:47:37,890 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:47:37,890 INFO L93 Difference]: Finished difference Result 732 states and 907 transitions. [2024-11-18 13:47:37,890 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2024-11-18 13:47:37,891 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 25 states have (on average 2.24) internal successors, (56), 25 states have internal predecessors, (56), 15 states have call successors, (32), 3 states have call predecessors, (32), 2 states have return successors, (30), 13 states have call predecessors, (30), 13 states have call successors, (30) Word has length 101 [2024-11-18 13:47:37,891 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:47:37,893 INFO L225 Difference]: With dead ends: 732 [2024-11-18 13:47:37,893 INFO L226 Difference]: Without dead ends: 555 [2024-11-18 13:47:37,894 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 209 GetRequests, 175 SyntacticMatches, 0 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 190 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=313, Invalid=947, Unknown=0, NotChecked=0, Total=1260 [2024-11-18 13:47:37,894 INFO L432 NwaCegarLoop]: 45 mSDtfsCounter, 91 mSDsluCounter, 459 mSDsCounter, 0 mSdLazyCounter, 520 mSolverCounterSat, 118 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 96 SdHoareTripleChecker+Valid, 504 SdHoareTripleChecker+Invalid, 638 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 118 IncrementalHoareTripleChecker+Valid, 520 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:47:37,894 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [96 Valid, 504 Invalid, 638 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [118 Valid, 520 Invalid, 0 Unknown, 0 Unchecked, 2.1s Time] [2024-11-18 13:47:37,895 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 555 states. [2024-11-18 13:47:38,031 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 555 to 490. [2024-11-18 13:47:38,031 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 490 states, 328 states have (on average 1.1829268292682926) internal successors, (388), 341 states have internal predecessors, (388), 98 states have call successors, (98), 64 states have call predecessors, (98), 63 states have return successors, (94), 84 states have call predecessors, (94), 94 states have call successors, (94) [2024-11-18 13:47:38,033 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 490 states to 490 states and 580 transitions. [2024-11-18 13:47:38,033 INFO L78 Accepts]: Start accepts. Automaton has 490 states and 580 transitions. Word has length 101 [2024-11-18 13:47:38,034 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:47:38,034 INFO L471 AbstractCegarLoop]: Abstraction has 490 states and 580 transitions. [2024-11-18 13:47:38,034 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 25 states have (on average 2.24) internal successors, (56), 25 states have internal predecessors, (56), 15 states have call successors, (32), 3 states have call predecessors, (32), 2 states have return successors, (30), 13 states have call predecessors, (30), 13 states have call successors, (30) [2024-11-18 13:47:38,034 INFO L276 IsEmpty]: Start isEmpty. Operand 490 states and 580 transitions. [2024-11-18 13:47:38,034 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 107 [2024-11-18 13:47:38,035 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:47:38,035 INFO L215 NwaCegarLoop]: trace histogram [17, 16, 16, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:47:38,050 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2024-11-18 13:47:38,236 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,SelfDestructingSolverStorable16 [2024-11-18 13:47:38,236 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:47:38,236 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:47:38,236 INFO L85 PathProgramCache]: Analyzing trace with hash -1040094269, now seen corresponding path program 2 times [2024-11-18 13:47:38,237 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:47:38,237 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [711529926] [2024-11-18 13:47:38,237 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:47:38,237 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:47:38,268 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:47:38,268 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:47:38,566 INFO L134 CoverageAnalysis]: Checked inductivity of 546 backedges. 32 proven. 34 refuted. 0 times theorem prover too weak. 480 trivial. 0 not checked. [2024-11-18 13:47:38,566 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:47:38,566 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [711529926] [2024-11-18 13:47:38,566 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [711529926] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:47:38,566 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1736843002] [2024-11-18 13:47:38,566 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:47:38,566 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:47:38,567 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:47:38,568 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-18 13:47:38,570 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-18 13:47:38,620 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:47:38,620 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:47:38,621 INFO L255 TraceCheckSpWp]: Trace formula consists of 267 conjuncts, 45 conjuncts are in the unsatisfiable core [2024-11-18 13:47:38,623 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:47:38,905 INFO L134 CoverageAnalysis]: Checked inductivity of 546 backedges. 34 proven. 77 refuted. 0 times theorem prover too weak. 435 trivial. 0 not checked. [2024-11-18 13:47:38,905 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:47:39,727 INFO L134 CoverageAnalysis]: Checked inductivity of 546 backedges. 34 proven. 77 refuted. 0 times theorem prover too weak. 435 trivial. 0 not checked. [2024-11-18 13:47:39,728 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1736843002] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:47:39,728 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 13:47:39,728 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 14, 10] total 24 [2024-11-18 13:47:39,728 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1172507704] [2024-11-18 13:47:39,728 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 13:47:39,728 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2024-11-18 13:47:39,728 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:47:39,729 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2024-11-18 13:47:39,729 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=105, Invalid=447, Unknown=0, NotChecked=0, Total=552 [2024-11-18 13:47:39,729 INFO L87 Difference]: Start difference. First operand 490 states and 580 transitions. Second operand has 24 states, 24 states have (on average 3.2083333333333335) internal successors, (77), 23 states have internal predecessors, (77), 15 states have call successors, (49), 3 states have call predecessors, (49), 2 states have return successors, (47), 15 states have call predecessors, (47), 15 states have call successors, (47) [2024-11-18 13:47:40,266 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:47:40,266 INFO L93 Difference]: Finished difference Result 562 states and 691 transitions. [2024-11-18 13:47:40,267 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-11-18 13:47:40,267 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 24 states have (on average 3.2083333333333335) internal successors, (77), 23 states have internal predecessors, (77), 15 states have call successors, (49), 3 states have call predecessors, (49), 2 states have return successors, (47), 15 states have call predecessors, (47), 15 states have call successors, (47) Word has length 106 [2024-11-18 13:47:40,267 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:47:40,269 INFO L225 Difference]: With dead ends: 562 [2024-11-18 13:47:40,269 INFO L226 Difference]: Without dead ends: 493 [2024-11-18 13:47:40,270 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 222 GetRequests, 197 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 178 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=139, Invalid=563, Unknown=0, NotChecked=0, Total=702 [2024-11-18 13:47:40,270 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 31 mSDsluCounter, 278 mSDsCounter, 0 mSdLazyCounter, 338 mSolverCounterSat, 39 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 36 SdHoareTripleChecker+Valid, 316 SdHoareTripleChecker+Invalid, 377 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 39 IncrementalHoareTripleChecker+Valid, 338 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-18 13:47:40,271 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [36 Valid, 316 Invalid, 377 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [39 Valid, 338 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-18 13:47:40,271 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 493 states. [2024-11-18 13:47:40,419 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 493 to 440. [2024-11-18 13:47:40,420 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 440 states, 290 states have (on average 1.1793103448275861) internal successors, (342), 310 states have internal predecessors, (342), 93 states have call successors, (93), 56 states have call predecessors, (93), 56 states have return successors, (87), 73 states have call predecessors, (87), 87 states have call successors, (87) [2024-11-18 13:47:40,422 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 440 states to 440 states and 522 transitions. [2024-11-18 13:47:40,423 INFO L78 Accepts]: Start accepts. Automaton has 440 states and 522 transitions. Word has length 106 [2024-11-18 13:47:40,423 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:47:40,423 INFO L471 AbstractCegarLoop]: Abstraction has 440 states and 522 transitions. [2024-11-18 13:47:40,423 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 24 states have (on average 3.2083333333333335) internal successors, (77), 23 states have internal predecessors, (77), 15 states have call successors, (49), 3 states have call predecessors, (49), 2 states have return successors, (47), 15 states have call predecessors, (47), 15 states have call successors, (47) [2024-11-18 13:47:40,423 INFO L276 IsEmpty]: Start isEmpty. Operand 440 states and 522 transitions. [2024-11-18 13:47:40,424 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 109 [2024-11-18 13:47:40,424 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:47:40,424 INFO L215 NwaCegarLoop]: trace histogram [17, 16, 16, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2024-11-18 13:47:40,437 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2024-11-18 13:47:40,624 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,SelfDestructingSolverStorable17 [2024-11-18 13:47:40,624 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:47:40,625 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:47:40,625 INFO L85 PathProgramCache]: Analyzing trace with hash 969385619, now seen corresponding path program 4 times [2024-11-18 13:47:40,625 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:47:40,625 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [522581421] [2024-11-18 13:47:40,625 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-18 13:47:40,625 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:47:40,658 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-18 13:47:40,658 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:47:40,659 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2088585690] [2024-11-18 13:47:40,659 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-18 13:47:40,659 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:47:40,659 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:47:40,661 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-18 13:47:40,663 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-18 13:47:40,725 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-18 13:47:40,725 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:47:40,727 INFO L255 TraceCheckSpWp]: Trace formula consists of 219 conjuncts, 62 conjuncts are in the unsatisfiable core [2024-11-18 13:47:40,728 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:47:52,764 INFO L134 CoverageAnalysis]: Checked inductivity of 560 backedges. 159 proven. 86 refuted. 0 times theorem prover too weak. 315 trivial. 0 not checked. [2024-11-18 13:47:52,765 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:48:14,266 WARN L286 SmtUtils]: Spent 8.01s on a formula simplification that was a NOOP. DAG size: 5 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify)