./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/ps6-ll_unwindbound50.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version c7c6ca5d 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/ps6-ll_unwindbound50.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 5bfe5681b6d73d5859a119345279b9da165675f4eb4d814fdf24f92881f7a27f --- Real Ultimate output --- This is Ultimate 0.2.5-?-c7c6ca5-m [2024-11-08 14:44:03,503 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-08 14:44:03,563 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-08 14:44:03,568 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-08 14:44:03,569 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-08 14:44:03,587 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-08 14:44:03,588 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-08 14:44:03,589 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-08 14:44:03,589 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-08 14:44:03,590 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-08 14:44:03,591 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-08 14:44:03,591 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-08 14:44:03,591 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-08 14:44:03,591 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-08 14:44:03,593 INFO L153 SettingsManager]: * Use SBE=true [2024-11-08 14:44:03,593 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-08 14:44:03,593 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-08 14:44:03,593 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-08 14:44:03,594 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-08 14:44:03,594 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-08 14:44:03,594 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-08 14:44:03,594 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-08 14:44:03,594 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-08 14:44:03,595 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-08 14:44:03,595 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-08 14:44:03,595 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-08 14:44:03,595 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-08 14:44:03,597 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-08 14:44:03,597 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-08 14:44:03,597 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-08 14:44:03,597 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-08 14:44:03,598 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-08 14:44:03,598 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-08 14:44:03,598 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-08 14:44:03,598 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-08 14:44:03,598 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-08 14:44:03,598 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-08 14:44:03,598 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-08 14:44:03,598 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-08 14:44:03,599 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-08 14:44:03,599 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-08 14:44:03,599 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-08 14:44:03,599 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 -> 5bfe5681b6d73d5859a119345279b9da165675f4eb4d814fdf24f92881f7a27f [2024-11-08 14:44:03,771 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-08 14:44:03,786 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-08 14:44:03,789 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-08 14:44:03,790 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-08 14:44:03,790 INFO L274 PluginConnector]: CDTParser initialized [2024-11-08 14:44:03,792 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/ps6-ll_unwindbound50.c [2024-11-08 14:44:05,044 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-08 14:44:05,183 INFO L384 CDTParser]: Found 1 translation units. [2024-11-08 14:44:05,184 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/ps6-ll_unwindbound50.c [2024-11-08 14:44:05,189 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/815985329/8874128f5c634f9d99c15f0b103b7130/FLAG1b4aea66f [2024-11-08 14:44:05,607 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/815985329/8874128f5c634f9d99c15f0b103b7130 [2024-11-08 14:44:05,609 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-08 14:44:05,610 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-08 14:44:05,611 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-08 14:44:05,611 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-08 14:44:05,616 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-08 14:44:05,617 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.11 02:44:05" (1/1) ... [2024-11-08 14:44:05,617 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7c750f3c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:44:05, skipping insertion in model container [2024-11-08 14:44:05,617 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.11 02:44:05" (1/1) ... [2024-11-08 14:44:05,636 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-08 14:44:05,767 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/ps6-ll_unwindbound50.c[458,471] [2024-11-08 14:44:05,782 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-08 14:44:05,788 INFO L200 MainTranslator]: Completed pre-run [2024-11-08 14:44:05,796 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/ps6-ll_unwindbound50.c[458,471] [2024-11-08 14:44:05,807 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-08 14:44:05,820 INFO L204 MainTranslator]: Completed translation [2024-11-08 14:44:05,820 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:44:05 WrapperNode [2024-11-08 14:44:05,820 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-08 14:44:05,821 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-08 14:44:05,821 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-08 14:44:05,821 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-08 14:44:05,826 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:44:05" (1/1) ... [2024-11-08 14:44:05,831 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:44:05" (1/1) ... [2024-11-08 14:44:05,843 INFO L138 Inliner]: procedures = 14, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 43 [2024-11-08 14:44:05,844 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-08 14:44:05,844 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-08 14:44:05,844 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-08 14:44:05,844 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-08 14:44:05,852 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:44:05" (1/1) ... [2024-11-08 14:44:05,852 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:44:05" (1/1) ... [2024-11-08 14:44:05,853 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:44:05" (1/1) ... [2024-11-08 14:44:05,861 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-08 14:44:05,861 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:44:05" (1/1) ... [2024-11-08 14:44:05,861 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:44:05" (1/1) ... [2024-11-08 14:44:05,863 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:44:05" (1/1) ... [2024-11-08 14:44:05,865 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:44:05" (1/1) ... [2024-11-08 14:44:05,866 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:44:05" (1/1) ... [2024-11-08 14:44:05,866 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:44:05" (1/1) ... [2024-11-08 14:44:05,867 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-08 14:44:05,868 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-08 14:44:05,868 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-08 14:44:05,868 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-08 14:44:05,869 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:44:05" (1/1) ... [2024-11-08 14:44:05,873 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-08 14:44:05,882 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:44:05,897 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-08 14:44:05,899 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-08 14:44:05,933 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-08 14:44:05,933 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-08 14:44:05,934 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-08 14:44:05,934 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-08 14:44:05,934 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-08 14:44:05,934 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-08 14:44:05,980 INFO L238 CfgBuilder]: Building ICFG [2024-11-08 14:44:05,982 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-08 14:44:06,073 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2024-11-08 14:44:06,073 INFO L287 CfgBuilder]: Performing block encoding [2024-11-08 14:44:06,082 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-08 14:44:06,083 INFO L316 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-08 14:44:06,083 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.11 02:44:06 BoogieIcfgContainer [2024-11-08 14:44:06,083 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-08 14:44:06,089 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-08 14:44:06,089 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-08 14:44:06,091 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-08 14:44:06,091 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 08.11 02:44:05" (1/3) ... [2024-11-08 14:44:06,092 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@13f4b905 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.11 02:44:06, skipping insertion in model container [2024-11-08 14:44:06,092 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:44:05" (2/3) ... [2024-11-08 14:44:06,093 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@13f4b905 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.11 02:44:06, skipping insertion in model container [2024-11-08 14:44:06,093 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.11 02:44:06" (3/3) ... [2024-11-08 14:44:06,094 INFO L112 eAbstractionObserver]: Analyzing ICFG ps6-ll_unwindbound50.c [2024-11-08 14:44:06,106 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-08 14:44:06,107 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-08 14:44:06,148 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-08 14:44:06,154 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;@786c0417, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-08 14:44:06,154 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-08 14:44:06,157 INFO L276 IsEmpty]: Start isEmpty. Operand has 20 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 15 states have internal predecessors, (20), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-08 14:44:06,161 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2024-11-08 14:44:06,162 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:44:06,162 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:44:06,163 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:44:06,170 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:44:06,170 INFO L85 PathProgramCache]: Analyzing trace with hash -579246775, now seen corresponding path program 1 times [2024-11-08 14:44:06,177 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:44:06,178 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1389688036] [2024-11-08 14:44:06,178 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:44:06,178 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:44:06,256 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:44:06,302 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-08 14:44:06,302 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:44:06,303 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1389688036] [2024-11-08 14:44:06,304 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1389688036] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:44:06,304 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:44:06,304 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-08 14:44:06,306 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [98388787] [2024-11-08 14:44:06,307 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:44:06,310 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-08 14:44:06,311 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:44:06,330 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-08 14:44:06,331 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-08 14:44:06,333 INFO L87 Difference]: Start difference. First operand has 20 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 15 states have internal predecessors, (20), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-08 14:44:06,347 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:44:06,348 INFO L93 Difference]: Finished difference Result 37 states and 51 transitions. [2024-11-08 14:44:06,349 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-08 14:44:06,350 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2024-11-08 14:44:06,350 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:44:06,354 INFO L225 Difference]: With dead ends: 37 [2024-11-08 14:44:06,355 INFO L226 Difference]: Without dead ends: 16 [2024-11-08 14:44:06,357 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-08 14:44:06,361 INFO L432 NwaCegarLoop]: 23 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, 23 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-08 14:44:06,363 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 23 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:44:06,375 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 16 states. [2024-11-08 14:44:06,388 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 16 to 16. [2024-11-08 14:44:06,389 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 16 states, 11 states have (on average 1.2727272727272727) internal successors, (14), 12 states have internal predecessors, (14), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-08 14:44:06,390 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 16 states to 16 states and 19 transitions. [2024-11-08 14:44:06,392 INFO L78 Accepts]: Start accepts. Automaton has 16 states and 19 transitions. Word has length 9 [2024-11-08 14:44:06,392 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:44:06,393 INFO L471 AbstractCegarLoop]: Abstraction has 16 states and 19 transitions. [2024-11-08 14:44:06,393 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-08 14:44:06,393 INFO L276 IsEmpty]: Start isEmpty. Operand 16 states and 19 transitions. [2024-11-08 14:44:06,393 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2024-11-08 14:44:06,394 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:44:06,394 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:44:06,394 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-08 14:44:06,395 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:44:06,396 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:44:06,396 INFO L85 PathProgramCache]: Analyzing trace with hash -1986551203, now seen corresponding path program 1 times [2024-11-08 14:44:06,396 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:44:06,396 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [689341435] [2024-11-08 14:44:06,396 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:44:06,396 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:44:06,419 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:44:06,498 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-08 14:44:06,498 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:44:06,498 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [689341435] [2024-11-08 14:44:06,498 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [689341435] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:44:06,499 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:44:06,499 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-08 14:44:06,499 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [204140100] [2024-11-08 14:44:06,499 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:44:06,500 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-08 14:44:06,500 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:44:06,500 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-08 14:44:06,500 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-08 14:44:06,501 INFO L87 Difference]: Start difference. First operand 16 states and 19 transitions. Second operand has 4 states, 4 states have (on average 2.25) internal successors, (9), 3 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-08 14:44:06,521 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:44:06,521 INFO L93 Difference]: Finished difference Result 26 states and 30 transitions. [2024-11-08 14:44:06,522 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-08 14:44:06,522 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.25) internal successors, (9), 3 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 10 [2024-11-08 14:44:06,522 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:44:06,523 INFO L225 Difference]: With dead ends: 26 [2024-11-08 14:44:06,523 INFO L226 Difference]: Without dead ends: 18 [2024-11-08 14:44:06,523 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-08 14:44:06,524 INFO L432 NwaCegarLoop]: 17 mSDtfsCounter, 0 mSDsluCounter, 28 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 45 SdHoareTripleChecker+Invalid, 8 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 8 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:44:06,524 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 45 Invalid, 8 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 8 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:44:06,525 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 18 states. [2024-11-08 14:44:06,527 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 18 to 18. [2024-11-08 14:44:06,527 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 14 states have internal predecessors, (16), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-08 14:44:06,527 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 18 states to 18 states and 21 transitions. [2024-11-08 14:44:06,528 INFO L78 Accepts]: Start accepts. Automaton has 18 states and 21 transitions. Word has length 10 [2024-11-08 14:44:06,528 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:44:06,528 INFO L471 AbstractCegarLoop]: Abstraction has 18 states and 21 transitions. [2024-11-08 14:44:06,528 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.25) internal successors, (9), 3 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-08 14:44:06,529 INFO L276 IsEmpty]: Start isEmpty. Operand 18 states and 21 transitions. [2024-11-08 14:44:06,529 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2024-11-08 14:44:06,529 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:44:06,530 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:44:06,530 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-08 14:44:06,530 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:44:06,531 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:44:06,531 INFO L85 PathProgramCache]: Analyzing trace with hash -1984763743, now seen corresponding path program 1 times [2024-11-08 14:44:06,531 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:44:06,531 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1212252222] [2024-11-08 14:44:06,531 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:44:06,532 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:44:06,573 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:44:06,578 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [737611286] [2024-11-08 14:44:06,579 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:44:06,579 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:44:06,579 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:44:06,584 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-08 14:44:06,585 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-08 14:44:06,658 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:44:06,660 INFO L255 TraceCheckSpWp]: Trace formula consists of 50 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-08 14:44:06,663 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:44:06,744 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-08 14:44:06,745 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-08 14:44:06,745 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:44:06,745 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1212252222] [2024-11-08 14:44:06,746 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:44:06,746 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [737611286] [2024-11-08 14:44:06,748 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [737611286] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:44:06,748 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:44:06,748 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-08 14:44:06,748 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1745830344] [2024-11-08 14:44:06,749 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:44:06,749 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:44:06,749 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:44:06,749 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:44:06,750 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-08 14:44:06,750 INFO L87 Difference]: Start difference. First operand 18 states and 21 transitions. Second operand has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 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-08 14:44:06,798 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:44:06,798 INFO L93 Difference]: Finished difference Result 28 states and 33 transitions. [2024-11-08 14:44:06,798 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 14:44:06,799 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 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-08 14:44:06,799 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:44:06,800 INFO L225 Difference]: With dead ends: 28 [2024-11-08 14:44:06,800 INFO L226 Difference]: Without dead ends: 24 [2024-11-08 14:44:06,801 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 6 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-08 14:44:06,802 INFO L432 NwaCegarLoop]: 16 mSDtfsCounter, 4 mSDsluCounter, 43 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 59 SdHoareTripleChecker+Invalid, 24 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 22 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:44:06,803 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 59 Invalid, 24 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:44:06,804 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2024-11-08 14:44:06,808 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2024-11-08 14:44:06,810 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 17 states have (on average 1.1764705882352942) internal successors, (20), 18 states have internal predecessors, (20), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-08 14:44:06,810 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 27 transitions. [2024-11-08 14:44:06,811 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 27 transitions. Word has length 10 [2024-11-08 14:44:06,811 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:44:06,811 INFO L471 AbstractCegarLoop]: Abstraction has 24 states and 27 transitions. [2024-11-08 14:44:06,812 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 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-08 14:44:06,812 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 27 transitions. [2024-11-08 14:44:06,812 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2024-11-08 14:44:06,812 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:44:06,812 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:44:06,825 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-08 14:44:07,016 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-08 14:44:07,017 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:44:07,017 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:44:07,017 INFO L85 PathProgramCache]: Analyzing trace with hash -69803837, now seen corresponding path program 1 times [2024-11-08 14:44:07,017 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:44:07,017 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1395541585] [2024-11-08 14:44:07,018 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:44:07,018 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:44:07,035 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:44:07,114 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-08 14:44:07,116 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:44:07,124 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-08 14:44:07,124 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:44:07,124 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1395541585] [2024-11-08 14:44:07,124 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1395541585] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:44:07,127 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1648516575] [2024-11-08 14:44:07,127 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:44:07,127 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:44:07,127 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:44:07,128 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-08 14:44:07,129 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-08 14:44:07,176 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:44:07,178 INFO L255 TraceCheckSpWp]: Trace formula consists of 71 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-08 14:44:07,179 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:44:07,212 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-08 14:44:07,212 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:44:07,256 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-08 14:44:07,257 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1648516575] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:44:07,257 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 14:44:07,257 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 4, 5] total 8 [2024-11-08 14:44:07,257 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1457805364] [2024-11-08 14:44:07,257 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 14:44:07,257 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-08 14:44:07,257 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:44:07,258 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-08 14:44:07,258 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2024-11-08 14:44:07,259 INFO L87 Difference]: Start difference. First operand 24 states and 27 transitions. Second operand has 8 states, 8 states have (on average 3.375) internal successors, (27), 8 states have internal predecessors, (27), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-08 14:44:07,330 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:44:07,330 INFO L93 Difference]: Finished difference Result 58 states and 68 transitions. [2024-11-08 14:44:07,331 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-08 14:44:07,331 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.375) internal successors, (27), 8 states have internal predecessors, (27), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 18 [2024-11-08 14:44:07,331 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:44:07,331 INFO L225 Difference]: With dead ends: 58 [2024-11-08 14:44:07,332 INFO L226 Difference]: Without dead ends: 50 [2024-11-08 14:44:07,332 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 34 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=40, Invalid=70, Unknown=0, NotChecked=0, Total=110 [2024-11-08 14:44:07,332 INFO L432 NwaCegarLoop]: 17 mSDtfsCounter, 23 mSDsluCounter, 50 mSDsCounter, 0 mSdLazyCounter, 30 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 67 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 30 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:44:07,333 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [23 Valid, 67 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 30 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:44:07,334 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2024-11-08 14:44:07,343 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 46. [2024-11-08 14:44:07,343 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 31 states have (on average 1.2258064516129032) internal successors, (38), 34 states have internal predecessors, (38), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-08 14:44:07,344 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 55 transitions. [2024-11-08 14:44:07,344 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 55 transitions. Word has length 18 [2024-11-08 14:44:07,344 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:44:07,344 INFO L471 AbstractCegarLoop]: Abstraction has 46 states and 55 transitions. [2024-11-08 14:44:07,344 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.375) internal successors, (27), 8 states have internal predecessors, (27), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-08 14:44:07,344 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 55 transitions. [2024-11-08 14:44:07,346 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2024-11-08 14:44:07,346 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:44:07,346 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:44:07,360 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-08 14:44:07,547 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-08 14:44:07,547 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:44:07,548 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:44:07,548 INFO L85 PathProgramCache]: Analyzing trace with hash -68016377, now seen corresponding path program 1 times [2024-11-08 14:44:07,548 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:44:07,548 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2002416412] [2024-11-08 14:44:07,548 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:44:07,548 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:44:07,566 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:44:07,566 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1896162463] [2024-11-08 14:44:07,567 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:44:07,567 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:44:07,567 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:44:07,570 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-08 14:44:07,571 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-08 14:44:07,611 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:44:07,612 INFO L255 TraceCheckSpWp]: Trace formula consists of 71 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-08 14:44:07,613 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:44:07,665 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-08 14:44:07,665 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:44:07,739 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-08 14:44:07,739 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:44:07,739 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2002416412] [2024-11-08 14:44:07,739 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:44:07,739 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1896162463] [2024-11-08 14:44:07,739 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1896162463] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-08 14:44:07,739 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-08 14:44:07,739 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2024-11-08 14:44:07,739 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1501711791] [2024-11-08 14:44:07,740 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:44:07,740 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:44:07,740 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:44:07,741 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:44:07,741 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-08 14:44:07,741 INFO L87 Difference]: Start difference. First operand 46 states and 55 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-08 14:44:07,775 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:44:07,776 INFO L93 Difference]: Finished difference Result 60 states and 68 transitions. [2024-11-08 14:44:07,776 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 14:44:07,776 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 18 [2024-11-08 14:44:07,776 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:44:07,777 INFO L225 Difference]: With dead ends: 60 [2024-11-08 14:44:07,777 INFO L226 Difference]: Without dead ends: 52 [2024-11-08 14:44:07,777 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 35 GetRequests, 27 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-08 14:44:07,778 INFO L432 NwaCegarLoop]: 14 mSDtfsCounter, 5 mSDsluCounter, 33 mSDsCounter, 0 mSdLazyCounter, 19 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 47 SdHoareTripleChecker+Invalid, 20 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 19 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:44:07,778 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 47 Invalid, 20 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 19 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:44:07,778 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2024-11-08 14:44:07,788 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 46. [2024-11-08 14:44:07,789 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 33 states have (on average 1.121212121212121) internal successors, (37), 35 states have internal predecessors, (37), 8 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (7), 5 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-08 14:44:07,790 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 52 transitions. [2024-11-08 14:44:07,790 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 52 transitions. Word has length 18 [2024-11-08 14:44:07,790 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:44:07,790 INFO L471 AbstractCegarLoop]: Abstraction has 46 states and 52 transitions. [2024-11-08 14:44:07,790 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-08 14:44:07,791 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 52 transitions. [2024-11-08 14:44:07,791 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-11-08 14:44:07,791 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:44:07,791 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:44:07,803 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-11-08 14:44:07,992 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-08 14:44:07,992 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:44:07,992 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:44:07,992 INFO L85 PathProgramCache]: Analyzing trace with hash 156635680, now seen corresponding path program 1 times [2024-11-08 14:44:07,992 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:44:07,993 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [731558458] [2024-11-08 14:44:07,993 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:44:07,993 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:44:08,007 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:44:08,008 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [23710767] [2024-11-08 14:44:08,008 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:44:08,008 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:44:08,009 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:44:08,012 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-08 14:44:08,013 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-08 14:44:08,048 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:44:08,049 INFO L255 TraceCheckSpWp]: Trace formula consists of 90 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-08 14:44:08,059 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:44:08,146 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-08 14:44:08,146 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:44:08,222 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-08 14:44:08,222 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:44:08,222 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [731558458] [2024-11-08 14:44:08,222 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:44:08,222 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [23710767] [2024-11-08 14:44:08,222 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [23710767] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:44:08,223 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 14:44:08,223 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2024-11-08 14:44:08,223 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [64645585] [2024-11-08 14:44:08,223 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 14:44:08,223 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-08 14:44:08,223 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:44:08,223 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-08 14:44:08,224 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2024-11-08 14:44:08,224 INFO L87 Difference]: Start difference. First operand 46 states and 52 transitions. Second operand has 10 states, 8 states have (on average 2.875) internal successors, (23), 9 states have internal predecessors, (23), 6 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-08 14:44:08,317 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:44:08,317 INFO L93 Difference]: Finished difference Result 55 states and 63 transitions. [2024-11-08 14:44:08,317 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-08 14:44:08,317 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 2.875) internal successors, (23), 9 states have internal predecessors, (23), 6 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Word has length 29 [2024-11-08 14:44:08,318 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:44:08,318 INFO L225 Difference]: With dead ends: 55 [2024-11-08 14:44:08,320 INFO L226 Difference]: Without dead ends: 46 [2024-11-08 14:44:08,320 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 59 GetRequests, 46 SyntacticMatches, 2 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=39, Invalid=117, Unknown=0, NotChecked=0, Total=156 [2024-11-08 14:44:08,321 INFO L432 NwaCegarLoop]: 21 mSDtfsCounter, 1 mSDsluCounter, 70 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 91 SdHoareTripleChecker+Invalid, 42 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:44:08,321 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 91 Invalid, 42 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:44:08,321 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2024-11-08 14:44:08,334 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 46. [2024-11-08 14:44:08,334 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 34 states have (on average 1.0588235294117647) internal successors, (36), 34 states have internal predecessors, (36), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-08 14:44:08,335 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 49 transitions. [2024-11-08 14:44:08,335 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 49 transitions. Word has length 29 [2024-11-08 14:44:08,335 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:44:08,335 INFO L471 AbstractCegarLoop]: Abstraction has 46 states and 49 transitions. [2024-11-08 14:44:08,336 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 2.875) internal successors, (23), 9 states have internal predecessors, (23), 6 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-08 14:44:08,336 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 49 transitions. [2024-11-08 14:44:08,336 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2024-11-08 14:44:08,336 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:44:08,337 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 5, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:44:08,349 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-11-08 14:44:08,540 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-08 14:44:08,541 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:44:08,541 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:44:08,541 INFO L85 PathProgramCache]: Analyzing trace with hash -1854611729, now seen corresponding path program 1 times [2024-11-08 14:44:08,541 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:44:08,541 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1132383220] [2024-11-08 14:44:08,541 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:44:08,541 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:44:08,554 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:44:08,663 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-08 14:44:08,665 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:44:08,668 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-11-08 14:44:08,669 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:44:08,675 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2024-11-08 14:44:08,678 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:44:08,680 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-11-08 14:44:08,682 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:44:08,685 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 38 [2024-11-08 14:44:08,685 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:44:08,687 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 10 proven. 32 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-08 14:44:08,687 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:44:08,687 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1132383220] [2024-11-08 14:44:08,687 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1132383220] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:44:08,687 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2018430188] [2024-11-08 14:44:08,687 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:44:08,687 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:44:08,688 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:44:08,689 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-08 14:44:08,690 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-08 14:44:08,733 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:44:08,734 INFO L255 TraceCheckSpWp]: Trace formula consists of 143 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-08 14:44:08,736 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:44:08,791 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 24 proven. 56 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-08 14:44:08,791 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:44:08,894 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 10 proven. 32 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-08 14:44:08,894 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2018430188] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:44:08,894 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 14:44:08,894 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7, 8] total 14 [2024-11-08 14:44:08,894 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1721537088] [2024-11-08 14:44:08,894 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 14:44:08,895 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-08 14:44:08,896 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:44:08,896 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-08 14:44:08,896 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2024-11-08 14:44:08,896 INFO L87 Difference]: Start difference. First operand 46 states and 49 transitions. Second operand has 14 states, 14 states have (on average 4.0) internal successors, (56), 14 states have internal predecessors, (56), 9 states have call successors, (15), 6 states have call predecessors, (15), 6 states have return successors, (14), 9 states have call predecessors, (14), 9 states have call successors, (14) [2024-11-08 14:44:09,070 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:44:09,070 INFO L93 Difference]: Finished difference Result 132 states and 144 transitions. [2024-11-08 14:44:09,071 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-11-08 14:44:09,071 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 4.0) internal successors, (56), 14 states have internal predecessors, (56), 9 states have call successors, (15), 6 states have call predecessors, (15), 6 states have return successors, (14), 9 states have call predecessors, (14), 9 states have call successors, (14) Word has length 47 [2024-11-08 14:44:09,071 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:44:09,072 INFO L225 Difference]: With dead ends: 132 [2024-11-08 14:44:09,072 INFO L226 Difference]: Without dead ends: 122 [2024-11-08 14:44:09,072 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 118 GetRequests, 97 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 55 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=184, Invalid=322, Unknown=0, NotChecked=0, Total=506 [2024-11-08 14:44:09,073 INFO L432 NwaCegarLoop]: 17 mSDtfsCounter, 77 mSDsluCounter, 89 mSDsCounter, 0 mSdLazyCounter, 69 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 77 SdHoareTripleChecker+Valid, 106 SdHoareTripleChecker+Invalid, 86 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 69 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 14:44:09,073 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [77 Valid, 106 Invalid, 86 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 69 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 14:44:09,074 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 122 states. [2024-11-08 14:44:09,090 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 122 to 97. [2024-11-08 14:44:09,090 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 97 states, 69 states have (on average 1.1014492753623188) internal successors, (76), 74 states have internal predecessors, (76), 17 states have call successors, (17), 11 states have call predecessors, (17), 10 states have return successors, (16), 11 states have call predecessors, (16), 16 states have call successors, (16) [2024-11-08 14:44:09,091 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 97 states to 97 states and 109 transitions. [2024-11-08 14:44:09,091 INFO L78 Accepts]: Start accepts. Automaton has 97 states and 109 transitions. Word has length 47 [2024-11-08 14:44:09,091 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:44:09,092 INFO L471 AbstractCegarLoop]: Abstraction has 97 states and 109 transitions. [2024-11-08 14:44:09,092 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 4.0) internal successors, (56), 14 states have internal predecessors, (56), 9 states have call successors, (15), 6 states have call predecessors, (15), 6 states have return successors, (14), 9 states have call predecessors, (14), 9 states have call successors, (14) [2024-11-08 14:44:09,092 INFO L276 IsEmpty]: Start isEmpty. Operand 97 states and 109 transitions. [2024-11-08 14:44:09,093 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 54 [2024-11-08 14:44:09,093 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:44:09,093 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 5, 5, 5, 5, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:44:09,107 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-08 14:44:09,296 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-08 14:44:09,297 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:44:09,297 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:44:09,297 INFO L85 PathProgramCache]: Analyzing trace with hash 348710830, now seen corresponding path program 2 times [2024-11-08 14:44:09,297 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:44:09,297 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [749155057] [2024-11-08 14:44:09,298 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:44:09,298 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:44:09,312 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:44:09,313 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1633193211] [2024-11-08 14:44:09,313 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-08 14:44:09,313 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:44:09,313 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:44:09,314 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-08 14:44:09,315 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-08 14:44:09,362 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-08 14:44:09,362 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 14:44:09,363 INFO L255 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 32 conjuncts are in the unsatisfiable core [2024-11-08 14:44:09,365 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:44:09,554 INFO L134 CoverageAnalysis]: Checked inductivity of 112 backedges. 12 proven. 40 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-11-08 14:44:09,554 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:44:09,795 INFO L134 CoverageAnalysis]: Checked inductivity of 112 backedges. 12 proven. 40 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-11-08 14:44:09,796 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:44:09,796 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [749155057] [2024-11-08 14:44:09,796 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:44:09,796 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1633193211] [2024-11-08 14:44:09,796 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1633193211] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:44:09,796 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 14:44:09,796 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 10] total 20 [2024-11-08 14:44:09,796 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1533887506] [2024-11-08 14:44:09,796 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 14:44:09,797 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-11-08 14:44:09,797 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:44:09,797 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-11-08 14:44:09,797 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=313, Unknown=0, NotChecked=0, Total=380 [2024-11-08 14:44:09,797 INFO L87 Difference]: Start difference. First operand 97 states and 109 transitions. Second operand has 20 states, 18 states have (on average 2.5) internal successors, (45), 18 states have internal predecessors, (45), 12 states have call successors, (14), 3 states have call predecessors, (14), 1 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-08 14:44:10,123 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:44:10,123 INFO L93 Difference]: Finished difference Result 103 states and 114 transitions. [2024-11-08 14:44:10,123 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-08 14:44:10,123 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 18 states have (on average 2.5) internal successors, (45), 18 states have internal predecessors, (45), 12 states have call successors, (14), 3 states have call predecessors, (14), 1 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Word has length 53 [2024-11-08 14:44:10,124 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:44:10,124 INFO L225 Difference]: With dead ends: 103 [2024-11-08 14:44:10,124 INFO L226 Difference]: Without dead ends: 92 [2024-11-08 14:44:10,125 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 114 GetRequests, 86 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 133 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=167, Invalid=703, Unknown=0, NotChecked=0, Total=870 [2024-11-08 14:44:10,125 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 24 mSDsluCounter, 222 mSDsCounter, 0 mSdLazyCounter, 146 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 254 SdHoareTripleChecker+Invalid, 153 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 146 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 14:44:10,126 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [26 Valid, 254 Invalid, 153 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 146 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 14:44:10,126 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2024-11-08 14:44:10,139 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 92. [2024-11-08 14:44:10,140 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 92 states, 69 states have (on average 1.0289855072463767) internal successors, (71), 69 states have internal predecessors, (71), 12 states have call successors, (12), 11 states have call predecessors, (12), 10 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-08 14:44:10,140 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 92 states to 92 states and 94 transitions. [2024-11-08 14:44:10,141 INFO L78 Accepts]: Start accepts. Automaton has 92 states and 94 transitions. Word has length 53 [2024-11-08 14:44:10,141 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:44:10,141 INFO L471 AbstractCegarLoop]: Abstraction has 92 states and 94 transitions. [2024-11-08 14:44:10,141 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 18 states have (on average 2.5) internal successors, (45), 18 states have internal predecessors, (45), 12 states have call successors, (14), 3 states have call predecessors, (14), 1 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-08 14:44:10,141 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states and 94 transitions. [2024-11-08 14:44:10,143 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 94 [2024-11-08 14:44:10,143 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:44:10,143 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 10, 10, 10, 10, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:44:10,155 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-08 14:44:10,343 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-08 14:44:10,344 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:44:10,344 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:44:10,344 INFO L85 PathProgramCache]: Analyzing trace with hash -1207691024, now seen corresponding path program 3 times [2024-11-08 14:44:10,344 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:44:10,344 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [309907528] [2024-11-08 14:44:10,344 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:44:10,345 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:44:10,391 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:44:10,392 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1427007782] [2024-11-08 14:44:10,396 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-08 14:44:10,396 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:44:10,396 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:44:10,397 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-08 14:44:10,400 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-08 14:44:10,519 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2024-11-08 14:44:10,519 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 14:44:10,521 INFO L255 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 54 conjuncts are in the unsatisfiable core [2024-11-08 14:44:10,525 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:44:10,757 INFO L134 CoverageAnalysis]: Checked inductivity of 422 backedges. 45 proven. 187 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2024-11-08 14:44:10,758 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:44:18,883 WARN L851 $PredicateComparison]: unable to prove that (let ((.cse0 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1|))) (or (= (+ |c_ULTIMATE.start_main_~y~0#1| .cse0) (+ |c_ULTIMATE.start_main_~c~0#1| (* |c_ULTIMATE.start_main_~c~0#1| |c_ULTIMATE.start_main_~y~0#1|))) (not (= 0 (mod (+ (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 10) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 7) .cse0 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 6)) 12))))) is different from false [2024-11-08 14:44:30,937 WARN L286 SmtUtils]: Spent 8.01s on a formula simplification that was a NOOP. DAG size: 4 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-08 14:44:44,493 WARN L286 SmtUtils]: Spent 8.01s on a formula simplification that was a NOOP. DAG size: 7 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-08 14:44:52,507 WARN L873 $PredicateComparison]: unable to prove that (or (not (= |c___VERIFIER_assert_#in~cond| 0)) (forall ((|v_ULTIMATE.start_main_~c~0#1_BEFORE_CALL_26| Int) (|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| Int)) (let ((.cse0 (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39|))) (or (= (+ |v_ULTIMATE.start_main_~c~0#1_BEFORE_CALL_26| (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~c~0#1_BEFORE_CALL_26|)) (+ |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| .cse0)) (= (mod (+ .cse0 (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| 7) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| 10) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| 6)) 12) 0))))) is different from true [2024-11-08 14:45:04,575 WARN L286 SmtUtils]: Spent 8.05s on a formula simplification that was a NOOP. DAG size: 7 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-08 14:45:20,605 WARN L286 SmtUtils]: Spent 8.00s on a formula simplification that was a NOOP. DAG size: 7 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-08 14:45:28,619 WARN L873 $PredicateComparison]: unable to prove that (or (not (= |c___VERIFIER_assert_#in~cond| 0)) (= c___VERIFIER_assert_~cond 0) (forall ((|v_ULTIMATE.start_main_~c~0#1_BEFORE_CALL_26| Int) (|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| Int)) (let ((.cse0 (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39|))) (or (= (+ |v_ULTIMATE.start_main_~c~0#1_BEFORE_CALL_26| (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~c~0#1_BEFORE_CALL_26|)) (+ |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| .cse0)) (= (mod (+ .cse0 (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| 7) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| 10) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| 6)) 12) 0))))) is different from true [2024-11-08 14:45:44,673 WARN L851 $PredicateComparison]: unable to prove that (let ((.cse0 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1|))) (or (not (= 0 (mod (+ (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 10) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 7) .cse0 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 6)) 12))) (= (+ .cse0 (* |c_ULTIMATE.start_main_~y~0#1| 2)) (+ (* |c_ULTIMATE.start_main_~c~0#1| 2) (* |c_ULTIMATE.start_main_~c~0#1| |c_ULTIMATE.start_main_~y~0#1|))))) is different from false