./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_valuebound2.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 023d838f Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_valuebound2.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 942b28ff7c0583b7db8395d2c315e70afc8fe68ba69d39faf867ac75d7628edb --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.fs.icfgbuilder-eval-023d838-m [2024-11-09 22:28:41,954 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-09 22:28:42,020 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-09 22:28:42,025 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-09 22:28:42,026 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-09 22:28:42,051 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-09 22:28:42,052 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-09 22:28:42,052 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-09 22:28:42,053 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-09 22:28:42,056 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-09 22:28:42,057 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-09 22:28:42,057 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-09 22:28:42,057 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-09 22:28:42,058 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-09 22:28:42,058 INFO L153 SettingsManager]: * Use SBE=true [2024-11-09 22:28:42,058 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-09 22:28:42,058 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-09 22:28:42,058 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-09 22:28:42,059 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-09 22:28:42,059 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-09 22:28:42,061 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-09 22:28:42,061 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-09 22:28:42,061 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-09 22:28:42,062 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-09 22:28:42,062 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-09 22:28:42,062 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-09 22:28:42,062 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-09 22:28:42,063 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-09 22:28:42,063 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2024-11-09 22:28:42,063 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-09 22:28:42,063 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-09 22:28:42,064 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-09 22:28:42,064 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-09 22:28:42,064 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-09 22:28:42,064 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-09 22:28:42,065 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-09 22:28:42,065 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-09 22:28:42,065 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-09 22:28:42,065 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-09 22:28:42,066 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-09 22:28:42,066 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-09 22:28:42,066 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-09 22:28:42,066 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 -> 942b28ff7c0583b7db8395d2c315e70afc8fe68ba69d39faf867ac75d7628edb [2024-11-09 22:28:42,309 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-09 22:28:42,334 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-09 22:28:42,338 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-09 22:28:42,339 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-09 22:28:42,339 INFO L274 PluginConnector]: CDTParser initialized [2024-11-09 22:28:42,340 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_valuebound2.c [2024-11-09 22:28:43,687 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-09 22:28:43,870 INFO L384 CDTParser]: Found 1 translation units. [2024-11-09 22:28:43,873 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_valuebound2.c [2024-11-09 22:28:43,880 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/66f0d504d/27ce0f1f8ab94effb6bffcee509a27ee/FLAG8ed187564 [2024-11-09 22:28:44,252 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/66f0d504d/27ce0f1f8ab94effb6bffcee509a27ee [2024-11-09 22:28:44,255 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-09 22:28:44,256 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-09 22:28:44,257 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-09 22:28:44,257 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-09 22:28:44,263 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-09 22:28:44,263 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 10:28:44" (1/1) ... [2024-11-09 22:28:44,264 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@55e1b4ff and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:28:44, skipping insertion in model container [2024-11-09 22:28:44,264 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 10:28:44" (1/1) ... [2024-11-09 22:28:44,283 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-09 22:28:44,448 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_valuebound2.c[588,601] [2024-11-09 22:28:44,466 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 22:28:44,475 INFO L200 MainTranslator]: Completed pre-run [2024-11-09 22:28:44,485 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_valuebound2.c[588,601] [2024-11-09 22:28:44,497 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 22:28:44,510 INFO L204 MainTranslator]: Completed translation [2024-11-09 22:28:44,511 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:28:44 WrapperNode [2024-11-09 22:28:44,511 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-09 22:28:44,512 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-09 22:28:44,512 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-09 22:28:44,513 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-09 22:28:44,518 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:28:44" (1/1) ... [2024-11-09 22:28:44,523 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:28:44" (1/1) ... [2024-11-09 22:28:44,545 INFO L138 Inliner]: procedures = 14, calls = 19, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 47 [2024-11-09 22:28:44,545 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-09 22:28:44,546 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-09 22:28:44,546 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-09 22:28:44,546 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-09 22:28:44,555 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:28:44" (1/1) ... [2024-11-09 22:28:44,555 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:28:44" (1/1) ... [2024-11-09 22:28:44,559 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:28:44" (1/1) ... [2024-11-09 22:28:44,573 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-11-09 22:28:44,573 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:28:44" (1/1) ... [2024-11-09 22:28:44,574 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:28:44" (1/1) ... [2024-11-09 22:28:44,576 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:28:44" (1/1) ... [2024-11-09 22:28:44,577 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:28:44" (1/1) ... [2024-11-09 22:28:44,577 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:28:44" (1/1) ... [2024-11-09 22:28:44,578 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:28:44" (1/1) ... [2024-11-09 22:28:44,579 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-09 22:28:44,580 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2024-11-09 22:28:44,580 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2024-11-09 22:28:44,581 INFO L274 PluginConnector]: IcfgBuilder initialized [2024-11-09 22:28:44,581 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:28:44" (1/1) ... [2024-11-09 22:28:44,587 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-09 22:28:44,599 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:28:44,618 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-09 22:28:44,625 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-09 22:28:44,669 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-09 22:28:44,669 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-09 22:28:44,670 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-09 22:28:44,670 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-09 22:28:44,670 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-09 22:28:44,671 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-09 22:28:44,738 INFO L256 CfgBuilder]: Building ICFG [2024-11-09 22:28:44,740 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-09 22:28:45,009 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-11-09 22:28:45,009 INFO L307 CfgBuilder]: Performing block encoding [2024-11-09 22:28:45,035 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-09 22:28:45,035 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-09 22:28:45,036 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 09.11 10:28:45 BoogieIcfgContainer [2024-11-09 22:28:45,036 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2024-11-09 22:28:45,039 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-09 22:28:45,041 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-09 22:28:45,044 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-09 22:28:45,044 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 09.11 10:28:44" (1/3) ... [2024-11-09 22:28:45,045 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@b2db71d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 10:28:45, skipping insertion in model container [2024-11-09 22:28:45,046 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:28:44" (2/3) ... [2024-11-09 22:28:45,046 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@b2db71d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 10:28:45, skipping insertion in model container [2024-11-09 22:28:45,046 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 09.11 10:28:45" (3/3) ... [2024-11-09 22:28:45,048 INFO L112 eAbstractionObserver]: Analyzing ICFG cohencu-ll_valuebound2.c [2024-11-09 22:28:45,063 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-09 22:28:45,063 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-09 22:28:45,125 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-09 22:28:45,133 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;@7c43c417, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-09 22:28:45,133 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-09 22:28:45,137 INFO L276 IsEmpty]: Start isEmpty. Operand has 29 states, 15 states have (on average 1.4) internal successors, (21), 16 states have internal predecessors, (21), 11 states have call successors, (11), 1 states have call predecessors, (11), 1 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-09 22:28:45,144 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2024-11-09 22:28:45,145 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:28:45,145 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:28:45,146 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:28:45,150 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:28:45,152 INFO L85 PathProgramCache]: Analyzing trace with hash -429095500, now seen corresponding path program 1 times [2024-11-09 22:28:45,162 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:28:45,163 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [728293900] [2024-11-09 22:28:45,163 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:28:45,164 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:28:45,259 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:28:45,312 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-09 22:28:45,313 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:28:45,313 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [728293900] [2024-11-09 22:28:45,315 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [728293900] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:28:45,315 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:28:45,315 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-09 22:28:45,317 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1737296196] [2024-11-09 22:28:45,318 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:28:45,321 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-09 22:28:45,322 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:28:45,344 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-09 22:28:45,345 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-09 22:28:45,347 INFO L87 Difference]: Start difference. First operand has 29 states, 15 states have (on average 1.4) internal successors, (21), 16 states have internal predecessors, (21), 11 states have call successors, (11), 1 states have call predecessors, (11), 1 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 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-09 22:28:45,370 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:28:45,371 INFO L93 Difference]: Finished difference Result 55 states and 93 transitions. [2024-11-09 22:28:45,372 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-09 22:28:45,374 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 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-09 22:28:45,374 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:28:45,380 INFO L225 Difference]: With dead ends: 55 [2024-11-09 22:28:45,381 INFO L226 Difference]: Without dead ends: 25 [2024-11-09 22:28:45,384 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-09 22:28:45,389 INFO L432 NwaCegarLoop]: 39 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, 39 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-09 22:28:45,390 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 22:28:45,405 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2024-11-09 22:28:45,423 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 25. [2024-11-09 22:28:45,425 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 25 states, 12 states have (on average 1.1666666666666667) internal successors, (14), 13 states have internal predecessors, (14), 11 states have call successors, (11), 1 states have call predecessors, (11), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-09 22:28:45,427 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 35 transitions. [2024-11-09 22:28:45,429 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 35 transitions. Word has length 10 [2024-11-09 22:28:45,430 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:28:45,430 INFO L471 AbstractCegarLoop]: Abstraction has 25 states and 35 transitions. [2024-11-09 22:28:45,431 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 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-09 22:28:45,431 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 35 transitions. [2024-11-09 22:28:45,432 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2024-11-09 22:28:45,433 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:28:45,433 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:28:45,433 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-09 22:28:45,434 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:28:45,434 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:28:45,435 INFO L85 PathProgramCache]: Analyzing trace with hash 458970679, now seen corresponding path program 1 times [2024-11-09 22:28:45,435 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:28:45,436 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1876324036] [2024-11-09 22:28:45,436 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:28:45,436 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:28:45,469 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:28:45,703 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-09 22:28:45,704 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:28:45,704 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1876324036] [2024-11-09 22:28:45,704 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1876324036] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:28:45,705 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:28:45,705 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 22:28:45,705 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [998496693] [2024-11-09 22:28:45,705 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:28:45,706 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 22:28:45,707 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:28:45,707 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 22:28:45,708 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 22:28:45,708 INFO L87 Difference]: Start difference. First operand 25 states and 35 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, (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-09 22:28:45,854 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:28:45,854 INFO L93 Difference]: Finished difference Result 32 states and 41 transitions. [2024-11-09 22:28:45,855 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 22:28:45,855 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, (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 11 [2024-11-09 22:28:45,855 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:28:45,856 INFO L225 Difference]: With dead ends: 32 [2024-11-09 22:28:45,856 INFO L226 Difference]: Without dead ends: 29 [2024-11-09 22:28:45,856 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-09 22:28:45,857 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 4 mSDsluCounter, 64 mSDsCounter, 0 mSdLazyCounter, 30 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 93 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 30 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 22:28:45,858 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 93 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 30 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 22:28:45,859 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2024-11-09 22:28:45,870 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 29. [2024-11-09 22:28:45,870 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 15 states have (on average 1.1333333333333333) internal successors, (17), 16 states have internal predecessors, (17), 11 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-09 22:28:45,872 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 38 transitions. [2024-11-09 22:28:45,872 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 38 transitions. Word has length 11 [2024-11-09 22:28:45,872 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:28:45,872 INFO L471 AbstractCegarLoop]: Abstraction has 29 states and 38 transitions. [2024-11-09 22:28:45,872 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, (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-09 22:28:45,873 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 38 transitions. [2024-11-09 22:28:45,875 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2024-11-09 22:28:45,876 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:28:45,876 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:28:45,876 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-09 22:28:45,877 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:28:45,879 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:28:45,879 INFO L85 PathProgramCache]: Analyzing trace with hash 1353465059, now seen corresponding path program 1 times [2024-11-09 22:28:45,880 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:28:45,881 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1953254068] [2024-11-09 22:28:45,882 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:28:45,882 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:28:45,913 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:28:45,915 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1666271964] [2024-11-09 22:28:45,915 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:28:45,916 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:28:45,916 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:28:45,918 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-09 22:28:45,919 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-09 22:28:45,967 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:28:45,970 INFO L255 TraceCheckSpWp]: Trace formula consists of 57 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 22:28:45,975 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:28:46,073 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-09 22:28:46,074 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 22:28:46,074 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:28:46,074 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1953254068] [2024-11-09 22:28:46,075 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:28:46,075 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1666271964] [2024-11-09 22:28:46,075 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1666271964] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:28:46,075 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:28:46,076 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 22:28:46,076 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1327916784] [2024-11-09 22:28:46,076 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:28:46,077 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 22:28:46,077 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:28:46,078 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 22:28:46,078 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 22:28:46,078 INFO L87 Difference]: Start difference. First operand 29 states and 38 transitions. Second operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 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-09 22:28:46,142 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:28:46,142 INFO L93 Difference]: Finished difference Result 50 states and 69 transitions. [2024-11-09 22:28:46,143 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 22:28:46,143 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 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 16 [2024-11-09 22:28:46,143 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:28:46,144 INFO L225 Difference]: With dead ends: 50 [2024-11-09 22:28:46,144 INFO L226 Difference]: Without dead ends: 47 [2024-11-09 22:28:46,145 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 12 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-09 22:28:46,146 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 4 mSDsluCounter, 82 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 115 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-09 22:28:46,146 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 115 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 22:28:46,147 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2024-11-09 22:28:46,159 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 37. [2024-11-09 22:28:46,159 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 20 states have (on average 1.1) internal successors, (22), 22 states have internal predecessors, (22), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 11 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-09 22:28:46,160 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 47 transitions. [2024-11-09 22:28:46,161 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 47 transitions. Word has length 16 [2024-11-09 22:28:46,161 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:28:46,161 INFO L471 AbstractCegarLoop]: Abstraction has 37 states and 47 transitions. [2024-11-09 22:28:46,161 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 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-09 22:28:46,161 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 47 transitions. [2024-11-09 22:28:46,162 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2024-11-09 22:28:46,162 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:28:46,162 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:28:46,175 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-09 22:28:46,363 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:28:46,363 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:28:46,364 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:28:46,364 INFO L85 PathProgramCache]: Analyzing trace with hash -1980317321, now seen corresponding path program 1 times [2024-11-09 22:28:46,364 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:28:46,364 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [621991669] [2024-11-09 22:28:46,364 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:28:46,364 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:28:46,392 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:28:46,397 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [294400836] [2024-11-09 22:28:46,397 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:28:46,401 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:28:46,401 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:28:46,404 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-09 22:28:46,405 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-09 22:28:46,454 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:28:46,455 INFO L255 TraceCheckSpWp]: Trace formula consists of 66 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 22:28:46,456 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:28:46,523 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-09 22:28:46,523 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 22:28:46,523 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:28:46,523 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [621991669] [2024-11-09 22:28:46,524 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:28:46,524 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [294400836] [2024-11-09 22:28:46,524 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [294400836] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:28:46,524 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:28:46,524 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 22:28:46,525 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1827060812] [2024-11-09 22:28:46,525 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:28:46,525 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 22:28:46,525 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:28:46,526 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 22:28:46,526 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 22:28:46,526 INFO L87 Difference]: Start difference. First operand 37 states and 47 transitions. Second operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 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-09 22:28:46,596 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:28:46,597 INFO L93 Difference]: Finished difference Result 54 states and 72 transitions. [2024-11-09 22:28:46,597 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 22:28:46,597 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 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 21 [2024-11-09 22:28:46,598 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:28:46,599 INFO L225 Difference]: With dead ends: 54 [2024-11-09 22:28:46,599 INFO L226 Difference]: Without dead ends: 51 [2024-11-09 22:28:46,599 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 21 GetRequests, 17 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-09 22:28:46,600 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 4 mSDsluCounter, 80 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 112 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-09 22:28:46,601 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 112 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 22:28:46,601 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2024-11-09 22:28:46,623 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 47. [2024-11-09 22:28:46,623 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 47 states, 24 states have (on average 1.125) internal successors, (27), 26 states have internal predecessors, (27), 18 states have call successors, (18), 4 states have call predecessors, (18), 4 states have return successors, (17), 16 states have call predecessors, (17), 17 states have call successors, (17) [2024-11-09 22:28:46,624 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 62 transitions. [2024-11-09 22:28:46,625 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 62 transitions. Word has length 21 [2024-11-09 22:28:46,625 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:28:46,625 INFO L471 AbstractCegarLoop]: Abstraction has 47 states and 62 transitions. [2024-11-09 22:28:46,625 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 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-09 22:28:46,625 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 62 transitions. [2024-11-09 22:28:46,626 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2024-11-09 22:28:46,626 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:28:46,626 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-09 22:28:46,644 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-09 22:28:46,827 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable3 [2024-11-09 22:28:46,827 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:28:46,828 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:28:46,828 INFO L85 PathProgramCache]: Analyzing trace with hash -945415901, now seen corresponding path program 1 times [2024-11-09 22:28:46,828 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:28:46,828 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [864425409] [2024-11-09 22:28:46,828 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:28:46,829 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:28:46,860 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:28:46,862 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1509881313] [2024-11-09 22:28:46,862 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:28:46,862 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:28:46,863 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:28:46,864 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-09 22:28:46,870 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-09 22:28:46,916 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:28:46,918 INFO L255 TraceCheckSpWp]: Trace formula consists of 75 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-09 22:28:46,919 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:28:47,026 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-09 22:28:47,027 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 22:28:47,027 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:28:47,028 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [864425409] [2024-11-09 22:28:47,028 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:28:47,028 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1509881313] [2024-11-09 22:28:47,028 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1509881313] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:28:47,028 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:28:47,029 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 22:28:47,029 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1571405977] [2024-11-09 22:28:47,029 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:28:47,030 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 22:28:47,030 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:28:47,031 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 22:28:47,031 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 22:28:47,032 INFO L87 Difference]: Start difference. First operand 47 states and 62 transitions. Second operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 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-09 22:28:47,140 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:28:47,141 INFO L93 Difference]: Finished difference Result 62 states and 78 transitions. [2024-11-09 22:28:47,141 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 22:28:47,141 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 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 26 [2024-11-09 22:28:47,142 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:28:47,142 INFO L225 Difference]: With dead ends: 62 [2024-11-09 22:28:47,145 INFO L226 Difference]: Without dead ends: 49 [2024-11-09 22:28:47,146 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 26 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-09 22:28:47,147 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 4 mSDsluCounter, 75 mSDsCounter, 0 mSdLazyCounter, 43 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 104 SdHoareTripleChecker+Invalid, 49 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 43 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 22:28:47,147 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 104 Invalid, 49 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 43 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 22:28:47,148 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2024-11-09 22:28:47,164 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 49. [2024-11-09 22:28:47,165 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 49 states, 27 states have (on average 1.0740740740740742) internal successors, (29), 28 states have internal predecessors, (29), 16 states have call successors, (16), 5 states have call predecessors, (16), 5 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2024-11-09 22:28:47,169 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 60 transitions. [2024-11-09 22:28:47,171 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 60 transitions. Word has length 26 [2024-11-09 22:28:47,171 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:28:47,171 INFO L471 AbstractCegarLoop]: Abstraction has 49 states and 60 transitions. [2024-11-09 22:28:47,171 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 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-09 22:28:47,171 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 60 transitions. [2024-11-09 22:28:47,172 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2024-11-09 22:28:47,174 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:28:47,174 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:28:47,190 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-09 22:28:47,374 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:28:47,375 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:28:47,375 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:28:47,375 INFO L85 PathProgramCache]: Analyzing trace with hash -2137612214, now seen corresponding path program 1 times [2024-11-09 22:28:47,376 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:28:47,376 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [600960859] [2024-11-09 22:28:47,376 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:28:47,376 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:28:47,409 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:28:47,414 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [371512464] [2024-11-09 22:28:47,414 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:28:47,414 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:28:47,414 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:28:47,417 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-09 22:28:47,419 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-09 22:28:47,471 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:28:47,472 INFO L255 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 23 conjuncts are in the unsatisfiable core [2024-11-09 22:28:47,474 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:28:47,625 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 11 proven. 20 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-09 22:28:47,627 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:28:47,830 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 14 proven. 17 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-09 22:28:47,831 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:28:47,831 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [600960859] [2024-11-09 22:28:47,831 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:28:47,831 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [371512464] [2024-11-09 22:28:47,831 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [371512464] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:28:47,832 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 22:28:47,832 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2024-11-09 22:28:47,832 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1401300839] [2024-11-09 22:28:47,832 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 22:28:47,833 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-09 22:28:47,833 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:28:47,833 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-09 22:28:47,834 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=121, Unknown=0, NotChecked=0, Total=156 [2024-11-09 22:28:47,835 INFO L87 Difference]: Start difference. First operand 49 states and 60 transitions. Second operand has 13 states, 13 states have (on average 2.230769230769231) internal successors, (29), 11 states have internal predecessors, (29), 5 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 5 states have call successors, (12) [2024-11-09 22:28:48,097 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:28:48,097 INFO L93 Difference]: Finished difference Result 74 states and 94 transitions. [2024-11-09 22:28:48,098 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-09 22:28:48,098 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.230769230769231) internal successors, (29), 11 states have internal predecessors, (29), 5 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 5 states have call successors, (12) Word has length 44 [2024-11-09 22:28:48,098 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:28:48,101 INFO L225 Difference]: With dead ends: 74 [2024-11-09 22:28:48,101 INFO L226 Difference]: Without dead ends: 71 [2024-11-09 22:28:48,101 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 89 GetRequests, 75 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=56, Invalid=184, Unknown=0, NotChecked=0, Total=240 [2024-11-09 22:28:48,102 INFO L432 NwaCegarLoop]: 27 mSDtfsCounter, 11 mSDsluCounter, 153 mSDsCounter, 0 mSdLazyCounter, 194 mSolverCounterSat, 43 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 180 SdHoareTripleChecker+Invalid, 237 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 43 IncrementalHoareTripleChecker+Valid, 194 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-09 22:28:48,103 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 180 Invalid, 237 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [43 Valid, 194 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-09 22:28:48,103 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2024-11-09 22:28:48,120 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 57. [2024-11-09 22:28:48,121 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 33 states have (on average 1.0606060606060606) internal successors, (35), 34 states have internal predecessors, (35), 16 states have call successors, (16), 7 states have call predecessors, (16), 7 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2024-11-09 22:28:48,122 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 66 transitions. [2024-11-09 22:28:48,122 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 66 transitions. Word has length 44 [2024-11-09 22:28:48,122 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:28:48,123 INFO L471 AbstractCegarLoop]: Abstraction has 57 states and 66 transitions. [2024-11-09 22:28:48,123 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.230769230769231) internal successors, (29), 11 states have internal predecessors, (29), 5 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 5 states have call successors, (12) [2024-11-09 22:28:48,123 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 66 transitions. [2024-11-09 22:28:48,124 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2024-11-09 22:28:48,124 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:28:48,124 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:28:48,142 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-09 22:28:48,324 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:28:48,325 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:28:48,325 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:28:48,325 INFO L85 PathProgramCache]: Analyzing trace with hash 1540712048, now seen corresponding path program 2 times [2024-11-09 22:28:48,325 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:28:48,326 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1649699085] [2024-11-09 22:28:48,326 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:28:48,326 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:28:48,361 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:28:48,363 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [877494702] [2024-11-09 22:28:48,363 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-09 22:28:48,363 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:28:48,363 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:28:48,370 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-09 22:28:48,371 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-09 22:28:48,420 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-09 22:28:48,421 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 22:28:48,422 INFO L255 TraceCheckSpWp]: Trace formula consists of 122 conjuncts, 25 conjuncts are in the unsatisfiable core [2024-11-09 22:28:48,424 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:28:48,626 INFO L134 CoverageAnalysis]: Checked inductivity of 103 backedges. 28 proven. 9 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2024-11-09 22:28:48,627 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:28:48,830 INFO L134 CoverageAnalysis]: Checked inductivity of 103 backedges. 28 proven. 9 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2024-11-09 22:28:48,830 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:28:48,830 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1649699085] [2024-11-09 22:28:48,830 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:28:48,830 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [877494702] [2024-11-09 22:28:48,830 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [877494702] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:28:48,830 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 22:28:48,830 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 14 [2024-11-09 22:28:48,831 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [255196912] [2024-11-09 22:28:48,831 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 22:28:48,831 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-09 22:28:48,831 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:28:48,832 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-09 22:28:48,832 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=143, Unknown=0, NotChecked=0, Total=182 [2024-11-09 22:28:48,832 INFO L87 Difference]: Start difference. First operand 57 states and 66 transitions. Second operand has 14 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 11 states have internal predecessors, (29), 6 states have call successors, (16), 3 states have call predecessors, (16), 2 states have return successors, (14), 4 states have call predecessors, (14), 6 states have call successors, (14) [2024-11-09 22:28:49,121 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:28:49,121 INFO L93 Difference]: Finished difference Result 89 states and 107 transitions. [2024-11-09 22:28:49,121 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-09 22:28:49,121 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 11 states have internal predecessors, (29), 6 states have call successors, (16), 3 states have call predecessors, (16), 2 states have return successors, (14), 4 states have call predecessors, (14), 6 states have call successors, (14) Word has length 49 [2024-11-09 22:28:49,122 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:28:49,124 INFO L225 Difference]: With dead ends: 89 [2024-11-09 22:28:49,124 INFO L226 Difference]: Without dead ends: 83 [2024-11-09 22:28:49,125 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 100 GetRequests, 84 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 30 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=68, Invalid=238, Unknown=0, NotChecked=0, Total=306 [2024-11-09 22:28:49,125 INFO L432 NwaCegarLoop]: 27 mSDtfsCounter, 12 mSDsluCounter, 126 mSDsCounter, 0 mSdLazyCounter, 186 mSolverCounterSat, 74 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 153 SdHoareTripleChecker+Invalid, 260 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 74 IncrementalHoareTripleChecker+Valid, 186 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-09 22:28:49,126 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 153 Invalid, 260 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [74 Valid, 186 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-09 22:28:49,126 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 83 states. [2024-11-09 22:28:49,150 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 83 to 80. [2024-11-09 22:28:49,150 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 80 states, 45 states have (on average 1.0666666666666667) internal successors, (48), 47 states have internal predecessors, (48), 24 states have call successors, (24), 10 states have call predecessors, (24), 10 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2024-11-09 22:28:49,151 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 80 states to 80 states and 94 transitions. [2024-11-09 22:28:49,151 INFO L78 Accepts]: Start accepts. Automaton has 80 states and 94 transitions. Word has length 49 [2024-11-09 22:28:49,152 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:28:49,152 INFO L471 AbstractCegarLoop]: Abstraction has 80 states and 94 transitions. [2024-11-09 22:28:49,152 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 11 states have internal predecessors, (29), 6 states have call successors, (16), 3 states have call predecessors, (16), 2 states have return successors, (14), 4 states have call predecessors, (14), 6 states have call successors, (14) [2024-11-09 22:28:49,152 INFO L276 IsEmpty]: Start isEmpty. Operand 80 states and 94 transitions. [2024-11-09 22:28:49,154 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2024-11-09 22:28:49,154 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:28:49,154 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 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-09 22:28:49,171 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-09 22:28:49,358 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:28:49,359 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:28:49,359 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:28:49,359 INFO L85 PathProgramCache]: Analyzing trace with hash -1950321542, now seen corresponding path program 1 times [2024-11-09 22:28:49,359 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:28:49,359 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1914839928] [2024-11-09 22:28:49,359 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:28:49,360 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:28:49,401 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:28:49,408 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1692190785] [2024-11-09 22:28:49,408 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:28:49,408 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:28:49,408 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:28:49,412 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-09 22:28:49,414 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-09 22:28:49,469 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:28:49,470 INFO L255 TraceCheckSpWp]: Trace formula consists of 159 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-11-09 22:28:49,472 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:28:49,659 INFO L134 CoverageAnalysis]: Checked inductivity of 250 backedges. 22 proven. 8 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2024-11-09 22:28:49,659 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:28:50,135 INFO L134 CoverageAnalysis]: Checked inductivity of 250 backedges. 22 proven. 8 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2024-11-09 22:28:50,136 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:28:50,136 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1914839928] [2024-11-09 22:28:50,136 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:28:50,136 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1692190785] [2024-11-09 22:28:50,136 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1692190785] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:28:50,136 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 22:28:50,136 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2024-11-09 22:28:50,136 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1047471272] [2024-11-09 22:28:50,137 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 22:28:50,137 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-09 22:28:50,137 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:28:50,138 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-09 22:28:50,138 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2024-11-09 22:28:50,138 INFO L87 Difference]: Start difference. First operand 80 states and 94 transitions. Second operand has 10 states, 8 states have (on average 3.0) internal successors, (24), 9 states have internal predecessors, (24), 6 states have call successors, (24), 2 states have call predecessors, (24), 1 states have return successors, (22), 6 states have call predecessors, (22), 6 states have call successors, (22) [2024-11-09 22:28:50,472 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:28:50,472 INFO L93 Difference]: Finished difference Result 109 states and 131 transitions. [2024-11-09 22:28:50,472 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-09 22:28:50,473 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 3.0) internal successors, (24), 9 states have internal predecessors, (24), 6 states have call successors, (24), 2 states have call predecessors, (24), 1 states have return successors, (22), 6 states have call predecessors, (22), 6 states have call successors, (22) Word has length 70 [2024-11-09 22:28:50,473 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:28:50,475 INFO L225 Difference]: With dead ends: 109 [2024-11-09 22:28:50,476 INFO L226 Difference]: Without dead ends: 106 [2024-11-09 22:28:50,477 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 141 GetRequests, 128 SyntacticMatches, 2 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=41, Invalid=115, Unknown=0, NotChecked=0, Total=156 [2024-11-09 22:28:50,477 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 5 mSDsluCounter, 120 mSDsCounter, 0 mSdLazyCounter, 102 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 156 SdHoareTripleChecker+Invalid, 120 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 102 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-09 22:28:50,478 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 156 Invalid, 120 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 102 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-09 22:28:50,480 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 106 states. [2024-11-09 22:28:50,518 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 106 to 102. [2024-11-09 22:28:50,519 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 102 states, 57 states have (on average 1.0701754385964912) internal successors, (61), 60 states have internal predecessors, (61), 31 states have call successors, (31), 13 states have call predecessors, (31), 13 states have return successors, (29), 28 states have call predecessors, (29), 29 states have call successors, (29) [2024-11-09 22:28:50,519 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 102 states to 102 states and 121 transitions. [2024-11-09 22:28:50,520 INFO L78 Accepts]: Start accepts. Automaton has 102 states and 121 transitions. Word has length 70 [2024-11-09 22:28:50,520 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:28:50,520 INFO L471 AbstractCegarLoop]: Abstraction has 102 states and 121 transitions. [2024-11-09 22:28:50,521 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 3.0) internal successors, (24), 9 states have internal predecessors, (24), 6 states have call successors, (24), 2 states have call predecessors, (24), 1 states have return successors, (22), 6 states have call predecessors, (22), 6 states have call successors, (22) [2024-11-09 22:28:50,521 INFO L276 IsEmpty]: Start isEmpty. Operand 102 states and 121 transitions. [2024-11-09 22:28:50,522 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2024-11-09 22:28:50,522 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:28:50,522 INFO L215 NwaCegarLoop]: trace histogram [13, 12, 12, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:28:50,539 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-09 22:28:50,722 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:28:50,723 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:28:50,723 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:28:50,723 INFO L85 PathProgramCache]: Analyzing trace with hash -436515072, now seen corresponding path program 1 times [2024-11-09 22:28:50,723 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:28:50,723 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1489368259] [2024-11-09 22:28:50,724 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:28:50,724 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:28:50,763 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:28:50,764 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1003335328] [2024-11-09 22:28:50,764 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:28:50,765 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:28:50,765 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:28:50,769 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-09 22:28:50,770 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-09 22:28:50,827 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:28:50,828 INFO L255 TraceCheckSpWp]: Trace formula consists of 168 conjuncts, 26 conjuncts are in the unsatisfiable core [2024-11-09 22:28:50,832 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:28:51,158 INFO L134 CoverageAnalysis]: Checked inductivity of 296 backedges. 24 proven. 8 refuted. 0 times theorem prover too weak. 264 trivial. 0 not checked. [2024-11-09 22:28:51,158 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:28:51,544 INFO L134 CoverageAnalysis]: Checked inductivity of 296 backedges. 24 proven. 8 refuted. 0 times theorem prover too weak. 264 trivial. 0 not checked. [2024-11-09 22:28:51,545 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:28:51,545 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1489368259] [2024-11-09 22:28:51,545 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:28:51,545 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1003335328] [2024-11-09 22:28:51,545 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1003335328] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:28:51,545 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 22:28:51,545 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7] total 14 [2024-11-09 22:28:51,546 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1046953866] [2024-11-09 22:28:51,546 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 22:28:51,546 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-09 22:28:51,546 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:28:51,547 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-09 22:28:51,547 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=37, Invalid=145, Unknown=0, NotChecked=0, Total=182 [2024-11-09 22:28:51,547 INFO L87 Difference]: Start difference. First operand 102 states and 121 transitions. Second operand has 14 states, 12 states have (on average 2.3333333333333335) internal successors, (28), 12 states have internal predecessors, (28), 6 states have call successors, (26), 3 states have call predecessors, (26), 1 states have return successors, (24), 6 states have call predecessors, (24), 6 states have call successors, (24) [2024-11-09 22:28:52,011 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:28:52,011 INFO L93 Difference]: Finished difference Result 121 states and 140 transitions. [2024-11-09 22:28:52,012 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-09 22:28:52,012 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 12 states have (on average 2.3333333333333335) internal successors, (28), 12 states have internal predecessors, (28), 6 states have call successors, (26), 3 states have call predecessors, (26), 1 states have return successors, (24), 6 states have call predecessors, (24), 6 states have call successors, (24) Word has length 75 [2024-11-09 22:28:52,013 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:28:52,014 INFO L225 Difference]: With dead ends: 121 [2024-11-09 22:28:52,014 INFO L226 Difference]: Without dead ends: 111 [2024-11-09 22:28:52,014 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 154 GetRequests, 136 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 49 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=84, Invalid=296, Unknown=0, NotChecked=0, Total=380 [2024-11-09 22:28:52,015 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 17 mSDsluCounter, 210 mSDsCounter, 0 mSdLazyCounter, 161 mSolverCounterSat, 46 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 246 SdHoareTripleChecker+Invalid, 207 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 46 IncrementalHoareTripleChecker+Valid, 161 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-09 22:28:52,015 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 246 Invalid, 207 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [46 Valid, 161 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-09 22:28:52,019 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 111 states. [2024-11-09 22:28:52,073 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 111 to 108. [2024-11-09 22:28:52,073 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 108 states, 63 states have (on average 1.0476190476190477) internal successors, (66), 65 states have internal predecessors, (66), 29 states have call successors, (29), 15 states have call predecessors, (29), 15 states have return successors, (28), 27 states have call predecessors, (28), 28 states have call successors, (28) [2024-11-09 22:28:52,076 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 108 states to 108 states and 123 transitions. [2024-11-09 22:28:52,076 INFO L78 Accepts]: Start accepts. Automaton has 108 states and 123 transitions. Word has length 75 [2024-11-09 22:28:52,076 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:28:52,076 INFO L471 AbstractCegarLoop]: Abstraction has 108 states and 123 transitions. [2024-11-09 22:28:52,076 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 12 states have (on average 2.3333333333333335) internal successors, (28), 12 states have internal predecessors, (28), 6 states have call successors, (26), 3 states have call predecessors, (26), 1 states have return successors, (24), 6 states have call predecessors, (24), 6 states have call successors, (24) [2024-11-09 22:28:52,076 INFO L276 IsEmpty]: Start isEmpty. Operand 108 states and 123 transitions. [2024-11-09 22:28:52,079 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 83 [2024-11-09 22:28:52,079 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:28:52,079 INFO L215 NwaCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:28:52,096 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-09 22:28:52,279 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:28:52,280 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:28:52,280 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:28:52,280 INFO L85 PathProgramCache]: Analyzing trace with hash 597706225, now seen corresponding path program 3 times [2024-11-09 22:28:52,280 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:28:52,280 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1928899667] [2024-11-09 22:28:52,281 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:28:52,281 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:28:52,314 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:28:52,315 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1443803381] [2024-11-09 22:28:52,315 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-09 22:28:52,315 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:28:52,316 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:28:52,322 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-09 22:28:52,323 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-09 22:28:52,411 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-09 22:28:52,411 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 22:28:52,413 INFO L255 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 35 conjuncts are in the unsatisfiable core [2024-11-09 22:28:52,415 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:28:52,653 INFO L134 CoverageAnalysis]: Checked inductivity of 358 backedges. 55 proven. 27 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2024-11-09 22:28:52,657 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:28:53,523 INFO L134 CoverageAnalysis]: Checked inductivity of 358 backedges. 55 proven. 27 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2024-11-09 22:28:53,523 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:28:53,524 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1928899667] [2024-11-09 22:28:53,524 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:28:53,524 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1443803381] [2024-11-09 22:28:53,524 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1443803381] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:28:53,524 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 22:28:53,524 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9] total 16 [2024-11-09 22:28:53,525 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2098928527] [2024-11-09 22:28:53,525 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 22:28:53,525 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-09 22:28:53,525 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:28:53,526 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-09 22:28:53,538 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=52, Invalid=188, Unknown=0, NotChecked=0, Total=240 [2024-11-09 22:28:53,539 INFO L87 Difference]: Start difference. First operand 108 states and 123 transitions. Second operand has 16 states, 14 states have (on average 2.5) internal successors, (35), 13 states have internal predecessors, (35), 8 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 6 states have call predecessors, (26), 8 states have call successors, (26) [2024-11-09 22:28:59,114 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 5.20s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:28:59,459 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:28:59,459 INFO L93 Difference]: Finished difference Result 133 states and 147 transitions. [2024-11-09 22:28:59,460 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-09 22:28:59,460 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 14 states have (on average 2.5) internal successors, (35), 13 states have internal predecessors, (35), 8 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 6 states have call predecessors, (26), 8 states have call successors, (26) Word has length 82 [2024-11-09 22:28:59,460 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:28:59,461 INFO L225 Difference]: With dead ends: 133 [2024-11-09 22:28:59,461 INFO L226 Difference]: Without dead ends: 114 [2024-11-09 22:28:59,462 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 166 GetRequests, 148 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 31 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=80, Invalid=262, Unknown=0, NotChecked=0, Total=342 [2024-11-09 22:28:59,462 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 11 mSDsluCounter, 156 mSDsCounter, 0 mSdLazyCounter, 227 mSolverCounterSat, 68 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 190 SdHoareTripleChecker+Invalid, 296 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 68 IncrementalHoareTripleChecker+Valid, 227 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.6s IncrementalHoareTripleChecker+Time [2024-11-09 22:28:59,462 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 190 Invalid, 296 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [68 Valid, 227 Invalid, 1 Unknown, 0 Unchecked, 5.6s Time] [2024-11-09 22:28:59,463 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states. [2024-11-09 22:28:59,487 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 111. [2024-11-09 22:28:59,488 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 111 states, 69 states have (on average 1.0289855072463767) internal successors, (71), 70 states have internal predecessors, (71), 24 states have call successors, (24), 17 states have call predecessors, (24), 17 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2024-11-09 22:28:59,488 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 111 states to 111 states and 118 transitions. [2024-11-09 22:28:59,489 INFO L78 Accepts]: Start accepts. Automaton has 111 states and 118 transitions. Word has length 82 [2024-11-09 22:28:59,489 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:28:59,489 INFO L471 AbstractCegarLoop]: Abstraction has 111 states and 118 transitions. [2024-11-09 22:28:59,489 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 14 states have (on average 2.5) internal successors, (35), 13 states have internal predecessors, (35), 8 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 6 states have call predecessors, (26), 8 states have call successors, (26) [2024-11-09 22:28:59,490 INFO L276 IsEmpty]: Start isEmpty. Operand 111 states and 118 transitions. [2024-11-09 22:28:59,491 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 127 [2024-11-09 22:28:59,491 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:28:59,491 INFO L215 NwaCegarLoop]: trace histogram [22, 21, 21, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:28:59,501 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-09 22:28:59,695 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-11-09 22:28:59,696 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:28:59,696 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:28:59,697 INFO L85 PathProgramCache]: Analyzing trace with hash 1736778824, now seen corresponding path program 2 times [2024-11-09 22:28:59,697 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:28:59,697 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1940376419] [2024-11-09 22:28:59,697 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:28:59,697 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:28:59,745 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:28:59,747 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [645606780] [2024-11-09 22:28:59,747 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-09 22:28:59,747 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:28:59,748 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:28:59,753 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-09 22:28:59,754 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-09 22:28:59,826 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-09 22:28:59,826 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 22:28:59,828 INFO L255 TraceCheckSpWp]: Trace formula consists of 271 conjuncts, 45 conjuncts are in the unsatisfiable core [2024-11-09 22:28:59,831 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:29:00,189 INFO L134 CoverageAnalysis]: Checked inductivity of 930 backedges. 86 proven. 64 refuted. 0 times theorem prover too weak. 780 trivial. 0 not checked. [2024-11-09 22:29:00,190 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:29:00,921 INFO L134 CoverageAnalysis]: Checked inductivity of 930 backedges. 110 proven. 16 refuted. 0 times theorem prover too weak. 804 trivial. 0 not checked. [2024-11-09 22:29:00,922 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:29:00,922 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1940376419] [2024-11-09 22:29:00,922 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:29:00,922 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [645606780] [2024-11-09 22:29:00,922 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [645606780] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:29:00,922 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 22:29:00,922 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 8] total 17 [2024-11-09 22:29:00,923 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1772601887] [2024-11-09 22:29:00,923 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 22:29:00,923 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-09 22:29:00,923 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:29:00,924 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-09 22:29:00,924 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=52, Invalid=220, Unknown=0, NotChecked=0, Total=272 [2024-11-09 22:29:00,925 INFO L87 Difference]: Start difference. First operand 111 states and 118 transitions. Second operand has 17 states, 14 states have (on average 2.7142857142857144) internal successors, (38), 14 states have internal predecessors, (38), 10 states have call successors, (34), 3 states have call predecessors, (34), 2 states have return successors, (32), 8 states have call predecessors, (32), 9 states have call successors, (32) [2024-11-09 22:29:01,381 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:29:01,381 INFO L93 Difference]: Finished difference Result 145 states and 158 transitions. [2024-11-09 22:29:01,381 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-09 22:29:01,382 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 14 states have (on average 2.7142857142857144) internal successors, (38), 14 states have internal predecessors, (38), 10 states have call successors, (34), 3 states have call predecessors, (34), 2 states have return successors, (32), 8 states have call predecessors, (32), 9 states have call successors, (32) Word has length 126 [2024-11-09 22:29:01,382 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:29:01,383 INFO L225 Difference]: With dead ends: 145 [2024-11-09 22:29:01,383 INFO L226 Difference]: Without dead ends: 142 [2024-11-09 22:29:01,383 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 253 GetRequests, 235 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 36 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=70, Invalid=310, Unknown=0, NotChecked=0, Total=380 [2024-11-09 22:29:01,384 INFO L432 NwaCegarLoop]: 39 mSDtfsCounter, 10 mSDsluCounter, 213 mSDsCounter, 0 mSdLazyCounter, 274 mSolverCounterSat, 67 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 252 SdHoareTripleChecker+Invalid, 341 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 67 IncrementalHoareTripleChecker+Valid, 274 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-09 22:29:01,384 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 252 Invalid, 341 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [67 Valid, 274 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-09 22:29:01,385 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 142 states. [2024-11-09 22:29:01,432 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 142 to 119. [2024-11-09 22:29:01,433 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 119 states, 75 states have (on average 1.0266666666666666) internal successors, (77), 76 states have internal predecessors, (77), 24 states have call successors, (24), 19 states have call predecessors, (24), 19 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2024-11-09 22:29:01,434 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 119 states to 119 states and 124 transitions. [2024-11-09 22:29:01,434 INFO L78 Accepts]: Start accepts. Automaton has 119 states and 124 transitions. Word has length 126 [2024-11-09 22:29:01,435 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:29:01,436 INFO L471 AbstractCegarLoop]: Abstraction has 119 states and 124 transitions. [2024-11-09 22:29:01,436 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 14 states have (on average 2.7142857142857144) internal successors, (38), 14 states have internal predecessors, (38), 10 states have call successors, (34), 3 states have call predecessors, (34), 2 states have return successors, (32), 8 states have call predecessors, (32), 9 states have call successors, (32) [2024-11-09 22:29:01,436 INFO L276 IsEmpty]: Start isEmpty. Operand 119 states and 124 transitions. [2024-11-09 22:29:01,438 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 132 [2024-11-09 22:29:01,438 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:29:01,438 INFO L215 NwaCegarLoop]: trace histogram [23, 22, 22, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:29:01,458 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-11-09 22:29:01,638 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:29:01,639 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:29:01,639 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:29:01,639 INFO L85 PathProgramCache]: Analyzing trace with hash -1001238542, now seen corresponding path program 2 times [2024-11-09 22:29:01,639 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:29:01,639 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1956003142] [2024-11-09 22:29:01,640 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:29:01,640 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:29:01,668 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:29:01,674 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [574871927] [2024-11-09 22:29:01,674 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-09 22:29:01,674 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:29:01,674 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:29:01,676 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-09 22:29:01,679 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-09 22:29:01,750 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-09 22:29:01,750 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 22:29:01,751 INFO L255 TraceCheckSpWp]: Trace formula consists of 280 conjuncts, 37 conjuncts are in the unsatisfiable core [2024-11-09 22:29:01,754 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:29:01,991 INFO L134 CoverageAnalysis]: Checked inductivity of 1016 backedges. 88 proven. 67 refuted. 0 times theorem prover too weak. 861 trivial. 0 not checked. [2024-11-09 22:29:01,992 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:29:02,558 INFO L134 CoverageAnalysis]: Checked inductivity of 1016 backedges. 88 proven. 43 refuted. 0 times theorem prover too weak. 885 trivial. 0 not checked. [2024-11-09 22:29:02,558 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:29:02,559 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1956003142] [2024-11-09 22:29:02,559 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:29:02,559 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [574871927] [2024-11-09 22:29:02,559 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [574871927] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:29:02,559 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 22:29:02,559 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9] total 17 [2024-11-09 22:29:02,560 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [591009334] [2024-11-09 22:29:02,560 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 22:29:02,560 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-09 22:29:02,560 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:29:02,561 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-09 22:29:02,561 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=52, Invalid=220, Unknown=0, NotChecked=0, Total=272 [2024-11-09 22:29:02,561 INFO L87 Difference]: Start difference. First operand 119 states and 124 transitions. Second operand has 17 states, 15 states have (on average 2.533333333333333) internal successors, (38), 15 states have internal predecessors, (38), 9 states have call successors, (36), 3 states have call predecessors, (36), 2 states have return successors, (34), 8 states have call predecessors, (34), 9 states have call successors, (34) [2024-11-09 22:29:02,942 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:29:02,942 INFO L93 Difference]: Finished difference Result 153 states and 164 transitions. [2024-11-09 22:29:02,943 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-09 22:29:02,943 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 15 states have (on average 2.533333333333333) internal successors, (38), 15 states have internal predecessors, (38), 9 states have call successors, (36), 3 states have call predecessors, (36), 2 states have return successors, (34), 8 states have call predecessors, (34), 9 states have call successors, (34) Word has length 131 [2024-11-09 22:29:02,943 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:29:02,945 INFO L225 Difference]: With dead ends: 153 [2024-11-09 22:29:02,945 INFO L226 Difference]: Without dead ends: 148 [2024-11-09 22:29:02,946 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 267 GetRequests, 245 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 49 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=113, Invalid=439, Unknown=0, NotChecked=0, Total=552 [2024-11-09 22:29:02,947 INFO L432 NwaCegarLoop]: 39 mSDtfsCounter, 11 mSDsluCounter, 223 mSDsCounter, 0 mSdLazyCounter, 308 mSolverCounterSat, 44 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 262 SdHoareTripleChecker+Invalid, 352 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 44 IncrementalHoareTripleChecker+Valid, 308 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-09 22:29:02,947 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 262 Invalid, 352 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [44 Valid, 308 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-09 22:29:02,948 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 148 states. [2024-11-09 22:29:02,973 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 148 to 121. [2024-11-09 22:29:02,974 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 121 states, 77 states have (on average 1.0129870129870129) internal successors, (78), 77 states have internal predecessors, (78), 24 states have call successors, (24), 20 states have call predecessors, (24), 19 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2024-11-09 22:29:02,975 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 121 states to 121 states and 125 transitions. [2024-11-09 22:29:02,975 INFO L78 Accepts]: Start accepts. Automaton has 121 states and 125 transitions. Word has length 131 [2024-11-09 22:29:02,975 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:29:02,975 INFO L471 AbstractCegarLoop]: Abstraction has 121 states and 125 transitions. [2024-11-09 22:29:02,976 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 15 states have (on average 2.533333333333333) internal successors, (38), 15 states have internal predecessors, (38), 9 states have call successors, (36), 3 states have call predecessors, (36), 2 states have return successors, (34), 8 states have call predecessors, (34), 9 states have call successors, (34) [2024-11-09 22:29:02,976 INFO L276 IsEmpty]: Start isEmpty. Operand 121 states and 125 transitions. [2024-11-09 22:29:02,977 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 137 [2024-11-09 22:29:02,980 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:29:02,980 INFO L215 NwaCegarLoop]: trace histogram [24, 23, 23, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:29:02,997 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-09 22:29:03,180 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2024-11-09 22:29:03,181 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:29:03,181 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:29:03,181 INFO L85 PathProgramCache]: Analyzing trace with hash -560333240, now seen corresponding path program 1 times [2024-11-09 22:29:03,181 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:29:03,181 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1092619655] [2024-11-09 22:29:03,181 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:29:03,182 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:29:03,204 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:29:03,206 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1996094128] [2024-11-09 22:29:03,206 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:29:03,206 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:29:03,207 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:29:03,208 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-09 22:29:03,211 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-09 22:29:03,278 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:29:03,279 INFO L255 TraceCheckSpWp]: Trace formula consists of 289 conjuncts, 50 conjuncts are in the unsatisfiable core [2024-11-09 22:29:03,282 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:29:03,595 INFO L134 CoverageAnalysis]: Checked inductivity of 1106 backedges. 104 proven. 116 refuted. 0 times theorem prover too weak. 886 trivial. 0 not checked. [2024-11-09 22:29:03,595 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:29:25,540 INFO L134 CoverageAnalysis]: Checked inductivity of 1106 backedges. 104 proven. 116 refuted. 0 times theorem prover too weak. 886 trivial. 0 not checked. [2024-11-09 22:29:25,540 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:29:25,540 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1092619655] [2024-11-09 22:29:25,541 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:29:25,541 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1996094128] [2024-11-09 22:29:25,541 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1996094128] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:29:25,541 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 22:29:25,541 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 21 [2024-11-09 22:29:25,541 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1452722898] [2024-11-09 22:29:25,541 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 22:29:25,542 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-09 22:29:25,542 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:29:25,542 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-09 22:29:25,543 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=92, Invalid=328, Unknown=0, NotChecked=0, Total=420 [2024-11-09 22:29:25,543 INFO L87 Difference]: Start difference. First operand 121 states and 125 transitions. Second operand has 21 states, 17 states have (on average 2.5294117647058822) internal successors, (43), 17 states have internal predecessors, (43), 13 states have call successors, (48), 3 states have call predecessors, (48), 2 states have return successors, (46), 12 states have call predecessors, (46), 13 states have call successors, (46) [2024-11-09 22:29:29,786 WARN L851 $PredicateComparison]: unable to prove that (let ((.cse4 (* |c_ULTIMATE.start_main_~x~0#1| |c_ULTIMATE.start_main_~z~0#1|))) (let ((.cse5 (* |c_ULTIMATE.start_main_~n~0#1| |c_ULTIMATE.start_main_~y~0#1|)) (.cse6 (* (* |c_ULTIMATE.start_main_~n~0#1| |c_ULTIMATE.start_main_~x~0#1|) 6)) (.cse7 (* |c_ULTIMATE.start_main_~x~0#1| 6)) (.cse9 (* |c_ULTIMATE.start_main_~n~0#1| |c_ULTIMATE.start_main_~z~0#1|)) (.cse0 (* (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1|) 2)) (.cse1 (* |c_ULTIMATE.start_main_~z~0#1| |c_ULTIMATE.start_main_~z~0#1|)) (.cse3 (* .cse4 3)) (.cse2 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~z~0#1|))) (and (or (= (+ .cse0 8 (* .cse1 2) .cse2) (+ (* |c_ULTIMATE.start_main_~x~0#1| 36) .cse3 (* 7 |c_ULTIMATE.start_main_~z~0#1|) (* |c_ULTIMATE.start_main_~y~0#1| 46))) (not (= (+ .cse4 .cse2) (+ (* |c_ULTIMATE.start_main_~y~0#1| 6) (* .cse5 6) .cse6 .cse7)))) (let ((.cse8 (* 2 .cse2))) (or (not (= (+ .cse4 .cse8 .cse1) (+ (* |c_ULTIMATE.start_main_~y~0#1| 12) (* .cse9 6) (* 6 |c_ULTIMATE.start_main_~z~0#1|) .cse6 .cse7 (* .cse5 12)))) (= (+ .cse0 .cse8 (* 5 .cse1) 38) (+ (* |c_ULTIMATE.start_main_~y~0#1| 94) .cse3 (* 23 |c_ULTIMATE.start_main_~z~0#1|) (* |c_ULTIMATE.start_main_~x~0#1| 54))))) (= (+ (* 3 |c_ULTIMATE.start_main_~z~0#1|) .cse0) (+ (* |c_ULTIMATE.start_main_~y~0#1| 10) .cse3 (* |c_ULTIMATE.start_main_~x~0#1| 18) 10)) (let ((.cse10 (* 3 .cse2))) (or (not (= (+ .cse10 (* .cse1 3) .cse4) (+ (* .cse5 18) (* |c_ULTIMATE.start_main_~n~0#1| 36) (* |c_ULTIMATE.start_main_~y~0#1| 18) (* |c_ULTIMATE.start_main_~z~0#1| 12) 36 .cse6 .cse7 (* .cse9 18)))) (= (+ .cse10 .cse0 80 (* .cse1 9)) (+ (* 154 |c_ULTIMATE.start_main_~y~0#1|) .cse3 (* |c_ULTIMATE.start_main_~x~0#1| 72) (* |c_ULTIMATE.start_main_~z~0#1| 45)))))))) is different from false [2024-11-09 22:29:42,769 WARN L286 SmtUtils]: Spent 8.78s on a formula simplification that was a NOOP. DAG size: 97 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 22:30:06,559 WARN L286 SmtUtils]: Spent 18.20s on a formula simplification that was a NOOP. DAG size: 103 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 22:30:10,855 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:30:16,228 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 5.37s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers []