./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound20.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 023d838f Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound20.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 e587d407128aaafd417211e5ccf66790913a0bc1afeba03ae0cdb578f5831614 --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.fs.icfgbuilder-eval-023d838-m [2024-11-09 22:35:11,463 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-09 22:35:11,526 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-09 22:35:11,530 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-09 22:35:11,530 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-09 22:35:11,550 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-09 22:35:11,551 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-09 22:35:11,551 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-09 22:35:11,552 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-09 22:35:11,552 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-09 22:35:11,553 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-09 22:35:11,553 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-09 22:35:11,553 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-09 22:35:11,555 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-09 22:35:11,555 INFO L153 SettingsManager]: * Use SBE=true [2024-11-09 22:35:11,555 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-09 22:35:11,555 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-09 22:35:11,556 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-09 22:35:11,556 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-09 22:35:11,556 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-09 22:35:11,556 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-09 22:35:11,559 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-09 22:35:11,559 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-09 22:35:11,559 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-09 22:35:11,560 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-09 22:35:11,560 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-09 22:35:11,560 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-09 22:35:11,560 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-09 22:35:11,560 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2024-11-09 22:35:11,561 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-09 22:35:11,561 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-09 22:35:11,567 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-09 22:35:11,567 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-09 22:35:11,567 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-09 22:35:11,567 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-09 22:35:11,567 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-09 22:35:11,567 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-09 22:35:11,567 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-09 22:35:11,568 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-09 22:35:11,568 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-09 22:35:11,568 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-09 22:35:11,569 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-09 22:35:11,570 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 -> e587d407128aaafd417211e5ccf66790913a0bc1afeba03ae0cdb578f5831614 [2024-11-09 22:35:11,745 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-09 22:35:11,766 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-09 22:35:11,768 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-09 22:35:11,769 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-09 22:35:11,770 INFO L274 PluginConnector]: CDTParser initialized [2024-11-09 22:35:11,771 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound20.c [2024-11-09 22:35:12,982 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-09 22:35:13,102 INFO L384 CDTParser]: Found 1 translation units. [2024-11-09 22:35:13,103 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound20.c [2024-11-09 22:35:13,108 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/af8dd3900/4ac480f09187461c957eeaccc11613b2/FLAG5d0caee87 [2024-11-09 22:35:13,528 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/af8dd3900/4ac480f09187461c957eeaccc11613b2 [2024-11-09 22:35:13,530 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-09 22:35:13,531 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-09 22:35:13,532 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-09 22:35:13,532 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-09 22:35:13,536 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-09 22:35:13,536 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 10:35:13" (1/1) ... [2024-11-09 22:35:13,537 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@751564d2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:35:13, skipping insertion in model container [2024-11-09 22:35:13,537 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 10:35:13" (1/1) ... [2024-11-09 22:35:13,554 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-09 22:35:13,682 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/egcd2-ll_valuebound20.c[490,503] [2024-11-09 22:35:13,704 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 22:35:13,712 INFO L200 MainTranslator]: Completed pre-run [2024-11-09 22:35:13,722 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/egcd2-ll_valuebound20.c[490,503] [2024-11-09 22:35:13,734 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 22:35:13,749 INFO L204 MainTranslator]: Completed translation [2024-11-09 22:35:13,749 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:35:13 WrapperNode [2024-11-09 22:35:13,750 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-09 22:35:13,750 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-09 22:35:13,751 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-09 22:35:13,751 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-09 22:35:13,755 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:35:13" (1/1) ... [2024-11-09 22:35:13,761 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:35:13" (1/1) ... [2024-11-09 22:35:13,781 INFO L138 Inliner]: procedures = 14, calls = 19, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 77 [2024-11-09 22:35:13,781 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-09 22:35:13,781 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-09 22:35:13,782 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-09 22:35:13,782 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-09 22:35:13,788 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:35:13" (1/1) ... [2024-11-09 22:35:13,789 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:35:13" (1/1) ... [2024-11-09 22:35:13,790 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:35:13" (1/1) ... [2024-11-09 22:35:13,798 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-11-09 22:35:13,798 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:35:13" (1/1) ... [2024-11-09 22:35:13,799 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:35:13" (1/1) ... [2024-11-09 22:35:13,800 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:35:13" (1/1) ... [2024-11-09 22:35:13,801 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:35:13" (1/1) ... [2024-11-09 22:35:13,804 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:35:13" (1/1) ... [2024-11-09 22:35:13,805 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:35:13" (1/1) ... [2024-11-09 22:35:13,806 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-09 22:35:13,806 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2024-11-09 22:35:13,806 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2024-11-09 22:35:13,807 INFO L274 PluginConnector]: IcfgBuilder initialized [2024-11-09 22:35:13,807 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:35:13" (1/1) ... [2024-11-09 22:35:13,811 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-09 22:35:13,818 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:35:13,832 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-09 22:35:13,834 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-09 22:35:13,865 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-09 22:35:13,865 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-09 22:35:13,865 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-09 22:35:13,865 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-09 22:35:13,865 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-09 22:35:13,866 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-09 22:35:13,866 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-09 22:35:13,866 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-09 22:35:13,923 INFO L256 CfgBuilder]: Building ICFG [2024-11-09 22:35:13,925 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-09 22:35:14,079 INFO L? ?]: Removed 11 outVars from TransFormulas that were not future-live. [2024-11-09 22:35:14,079 INFO L307 CfgBuilder]: Performing block encoding [2024-11-09 22:35:14,094 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-09 22:35:14,095 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-09 22:35:14,096 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 09.11 10:35:14 BoogieIcfgContainer [2024-11-09 22:35:14,096 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2024-11-09 22:35:14,099 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-09 22:35:14,100 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-09 22:35:14,103 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-09 22:35:14,103 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 09.11 10:35:13" (1/3) ... [2024-11-09 22:35:14,104 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@12ec5ba6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 10:35:14, skipping insertion in model container [2024-11-09 22:35:14,104 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:35:13" (2/3) ... [2024-11-09 22:35:14,105 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@12ec5ba6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 10:35:14, skipping insertion in model container [2024-11-09 22:35:14,105 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 09.11 10:35:14" (3/3) ... [2024-11-09 22:35:14,106 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd2-ll_valuebound20.c [2024-11-09 22:35:14,120 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-09 22:35:14,120 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-09 22:35:14,170 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-09 22:35:14,177 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;@1499bf99, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-09 22:35:14,178 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-09 22:35:14,182 INFO L276 IsEmpty]: Start isEmpty. Operand has 38 states, 22 states have (on average 1.4090909090909092) internal successors, (31), 24 states have internal predecessors, (31), 12 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-09 22:35:14,187 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2024-11-09 22:35:14,188 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:35:14,189 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:35:14,190 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:35:14,194 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:35:14,195 INFO L85 PathProgramCache]: Analyzing trace with hash -1415255888, now seen corresponding path program 1 times [2024-11-09 22:35:14,203 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:35:14,204 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1452286400] [2024-11-09 22:35:14,204 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:35:14,204 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:35:14,284 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:14,325 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 22:35:14,327 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:14,332 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-09 22:35:14,336 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:14,342 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-09 22:35:14,344 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:14,346 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-09 22:35:14,347 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:14,350 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-09 22:35:14,351 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:14,353 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-09 22:35:14,354 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:14,358 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-11-09 22:35:14,358 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:35:14,359 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1452286400] [2024-11-09 22:35:14,359 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1452286400] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:35:14,359 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:35:14,360 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-09 22:35:14,361 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [955003329] [2024-11-09 22:35:14,361 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:35:14,365 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-09 22:35:14,366 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:35:14,381 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-09 22:35:14,381 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-09 22:35:14,383 INFO L87 Difference]: Start difference. First operand has 38 states, 22 states have (on average 1.4090909090909092) internal successors, (31), 24 states have internal predecessors, (31), 12 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 2 states have call successors, (6) [2024-11-09 22:35:14,398 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:35:14,398 INFO L93 Difference]: Finished difference Result 73 states and 118 transitions. [2024-11-09 22:35:14,399 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-09 22:35:14,399 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 2 states have call successors, (6) Word has length 40 [2024-11-09 22:35:14,400 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:35:14,404 INFO L225 Difference]: With dead ends: 73 [2024-11-09 22:35:14,404 INFO L226 Difference]: Without dead ends: 34 [2024-11-09 22:35:14,407 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 20 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-09 22:35:14,409 INFO L432 NwaCegarLoop]: 49 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, 49 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-09 22:35:14,409 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 49 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 22:35:14,423 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2024-11-09 22:35:14,435 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 34. [2024-11-09 22:35:14,436 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 19 states have (on average 1.1578947368421053) internal successors, (22), 21 states have internal predecessors, (22), 12 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-09 22:35:14,437 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 45 transitions. [2024-11-09 22:35:14,439 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 45 transitions. Word has length 40 [2024-11-09 22:35:14,439 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:35:14,439 INFO L471 AbstractCegarLoop]: Abstraction has 34 states and 45 transitions. [2024-11-09 22:35:14,439 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 2 states have call successors, (6) [2024-11-09 22:35:14,439 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 45 transitions. [2024-11-09 22:35:14,440 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2024-11-09 22:35:14,441 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:35:14,441 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:35:14,441 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-09 22:35:14,441 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:35:14,442 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:35:14,442 INFO L85 PathProgramCache]: Analyzing trace with hash 1274504883, now seen corresponding path program 1 times [2024-11-09 22:35:14,442 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:35:14,442 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2134431150] [2024-11-09 22:35:14,442 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:35:14,443 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:35:14,474 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:14,666 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 22:35:14,667 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:14,673 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-09 22:35:14,674 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:14,676 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-09 22:35:14,678 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:14,682 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-09 22:35:14,684 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:14,707 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-09 22:35:14,709 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:14,716 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-09 22:35:14,720 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:14,725 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 9 proven. 6 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-09 22:35:14,725 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:35:14,725 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2134431150] [2024-11-09 22:35:14,725 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2134431150] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 22:35:14,725 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [220153108] [2024-11-09 22:35:14,725 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:35:14,726 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:35:14,726 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:35:14,727 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:35:14,729 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-09 22:35:14,796 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:14,798 INFO L255 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-11-09 22:35:14,803 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:35:15,000 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 3 proven. 12 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-09 22:35:15,002 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:35:15,139 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [220153108] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 22:35:15,140 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 22:35:15,140 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 9] total 11 [2024-11-09 22:35:15,141 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [565988204] [2024-11-09 22:35:15,141 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 22:35:15,142 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-11-09 22:35:15,143 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:35:15,144 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-09 22:35:15,145 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=37, Invalid=173, Unknown=0, NotChecked=0, Total=210 [2024-11-09 22:35:15,145 INFO L87 Difference]: Start difference. First operand 34 states and 45 transitions. Second operand has 11 states, 10 states have (on average 2.3) internal successors, (23), 8 states have internal predecessors, (23), 6 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-09 22:35:15,345 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:35:15,346 INFO L93 Difference]: Finished difference Result 58 states and 75 transitions. [2024-11-09 22:35:15,346 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-09 22:35:15,346 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 2.3) internal successors, (23), 8 states have internal predecessors, (23), 6 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) Word has length 42 [2024-11-09 22:35:15,347 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:35:15,348 INFO L225 Difference]: With dead ends: 58 [2024-11-09 22:35:15,348 INFO L226 Difference]: Without dead ends: 49 [2024-11-09 22:35:15,348 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 54 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 33 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=55, Invalid=251, Unknown=0, NotChecked=0, Total=306 [2024-11-09 22:35:15,349 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 38 mSDsluCounter, 185 mSDsCounter, 0 mSdLazyCounter, 155 mSolverCounterSat, 23 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 38 SdHoareTripleChecker+Valid, 218 SdHoareTripleChecker+Invalid, 178 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 23 IncrementalHoareTripleChecker+Valid, 155 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 22:35:15,349 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [38 Valid, 218 Invalid, 178 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [23 Valid, 155 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 22:35:15,352 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2024-11-09 22:35:15,360 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 48. [2024-11-09 22:35:15,362 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 28 states have (on average 1.1428571428571428) internal successors, (32), 29 states have internal predecessors, (32), 16 states have call successors, (16), 3 states have call predecessors, (16), 3 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2024-11-09 22:35:15,365 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 63 transitions. [2024-11-09 22:35:15,365 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 63 transitions. Word has length 42 [2024-11-09 22:35:15,365 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:35:15,366 INFO L471 AbstractCegarLoop]: Abstraction has 48 states and 63 transitions. [2024-11-09 22:35:15,366 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 2.3) internal successors, (23), 8 states have internal predecessors, (23), 6 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-09 22:35:15,367 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 63 transitions. [2024-11-09 22:35:15,368 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2024-11-09 22:35:15,368 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:35:15,368 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:35:15,380 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-09 22:35:15,568 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:35:15,569 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:35:15,569 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:35:15,569 INFO L85 PathProgramCache]: Analyzing trace with hash -1060669222, now seen corresponding path program 1 times [2024-11-09 22:35:15,569 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:35:15,569 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [458371561] [2024-11-09 22:35:15,570 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:35:15,570 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:35:15,597 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:35:15,600 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1471586509] [2024-11-09 22:35:15,601 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:35:15,601 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:35:15,601 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:35:15,604 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:35:15,605 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-09 22:35:15,650 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:15,651 INFO L255 TraceCheckSpWp]: Trace formula consists of 118 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 22:35:15,652 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:35:15,699 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-11-09 22:35:15,699 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 22:35:15,700 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:35:15,700 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [458371561] [2024-11-09 22:35:15,700 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:35:15,700 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1471586509] [2024-11-09 22:35:15,700 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1471586509] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:35:15,700 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:35:15,700 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 22:35:15,701 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1614028817] [2024-11-09 22:35:15,701 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:35:15,701 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 22:35:15,701 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:35:15,701 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 22:35:15,701 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 22:35:15,702 INFO L87 Difference]: Start difference. First operand 48 states and 63 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2024-11-09 22:35:15,741 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:35:15,741 INFO L93 Difference]: Finished difference Result 70 states and 94 transitions. [2024-11-09 22:35:15,741 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 22:35:15,742 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) Word has length 44 [2024-11-09 22:35:15,743 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:35:15,744 INFO L225 Difference]: With dead ends: 70 [2024-11-09 22:35:15,744 INFO L226 Difference]: Without dead ends: 67 [2024-11-09 22:35:15,744 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 44 GetRequests, 40 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-09 22:35:15,745 INFO L432 NwaCegarLoop]: 39 mSDtfsCounter, 4 mSDsluCounter, 109 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 148 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-09 22:35:15,745 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 148 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 22:35:15,746 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2024-11-09 22:35:15,759 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 58. [2024-11-09 22:35:15,759 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 35 states have (on average 1.1142857142857143) internal successors, (39), 38 states have internal predecessors, (39), 18 states have call successors, (18), 4 states have call predecessors, (18), 4 states have return successors, (17), 15 states have call predecessors, (17), 17 states have call successors, (17) [2024-11-09 22:35:15,761 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 74 transitions. [2024-11-09 22:35:15,763 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 74 transitions. Word has length 44 [2024-11-09 22:35:15,763 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:35:15,763 INFO L471 AbstractCegarLoop]: Abstraction has 58 states and 74 transitions. [2024-11-09 22:35:15,763 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2024-11-09 22:35:15,763 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 74 transitions. [2024-11-09 22:35:15,764 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2024-11-09 22:35:15,765 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:35:15,765 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:35:15,779 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-09 22:35:15,966 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2024-11-09 22:35:15,966 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:35:15,967 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:35:15,967 INFO L85 PathProgramCache]: Analyzing trace with hash 952841133, now seen corresponding path program 1 times [2024-11-09 22:35:15,967 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:35:15,967 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [814885942] [2024-11-09 22:35:15,967 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:35:15,967 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:35:15,993 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:35:15,994 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1465468513] [2024-11-09 22:35:15,995 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:35:15,995 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:35:15,995 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:35:15,999 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:35:16,001 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-09 22:35:16,060 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:16,061 INFO L255 TraceCheckSpWp]: Trace formula consists of 127 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-09 22:35:16,063 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:35:16,157 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-11-09 22:35:16,158 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 22:35:16,158 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:35:16,159 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [814885942] [2024-11-09 22:35:16,159 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:35:16,159 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1465468513] [2024-11-09 22:35:16,159 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1465468513] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:35:16,159 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:35:16,160 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 22:35:16,160 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2081312186] [2024-11-09 22:35:16,160 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:35:16,161 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 22:35:16,161 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:35:16,162 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 22:35:16,163 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 22:35:16,163 INFO L87 Difference]: Start difference. First operand 58 states and 74 transitions. Second operand has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-09 22:35:16,205 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:35:16,206 INFO L93 Difference]: Finished difference Result 66 states and 81 transitions. [2024-11-09 22:35:16,206 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 22:35:16,207 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 49 [2024-11-09 22:35:16,208 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:35:16,210 INFO L225 Difference]: With dead ends: 66 [2024-11-09 22:35:16,210 INFO L226 Difference]: Without dead ends: 63 [2024-11-09 22:35:16,210 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 45 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-09 22:35:16,211 INFO L432 NwaCegarLoop]: 43 mSDtfsCounter, 5 mSDsluCounter, 115 mSDsCounter, 0 mSdLazyCounter, 27 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 158 SdHoareTripleChecker+Invalid, 27 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 27 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-09 22:35:16,213 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 158 Invalid, 27 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 22:35:16,213 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2024-11-09 22:35:16,226 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 62. [2024-11-09 22:35:16,226 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 38 states have (on average 1.105263157894737) internal successors, (42), 41 states have internal predecessors, (42), 18 states have call successors, (18), 5 states have call predecessors, (18), 5 states have return successors, (17), 15 states have call predecessors, (17), 17 states have call successors, (17) [2024-11-09 22:35:16,228 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 77 transitions. [2024-11-09 22:35:16,229 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 77 transitions. Word has length 49 [2024-11-09 22:35:16,229 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:35:16,230 INFO L471 AbstractCegarLoop]: Abstraction has 62 states and 77 transitions. [2024-11-09 22:35:16,230 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-09 22:35:16,230 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 77 transitions. [2024-11-09 22:35:16,231 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2024-11-09 22:35:16,231 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:35:16,231 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:35:16,243 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-09 22:35:16,432 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:35:16,432 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:35:16,433 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:35:16,433 INFO L85 PathProgramCache]: Analyzing trace with hash 1901382541, now seen corresponding path program 1 times [2024-11-09 22:35:16,433 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:35:16,433 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2091527900] [2024-11-09 22:35:16,433 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:35:16,433 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:35:16,461 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:35:16,466 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [639463077] [2024-11-09 22:35:16,466 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:35:16,466 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:35:16,466 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:35:16,468 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:35:16,472 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-09 22:35:16,521 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:16,524 INFO L255 TraceCheckSpWp]: Trace formula consists of 145 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-09 22:35:16,526 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:35:16,656 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 72 trivial. 0 not checked. [2024-11-09 22:35:16,657 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 22:35:16,657 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:35:16,657 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2091527900] [2024-11-09 22:35:16,657 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:35:16,657 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [639463077] [2024-11-09 22:35:16,657 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [639463077] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:35:16,658 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:35:16,658 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 22:35:16,658 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [634422769] [2024-11-09 22:35:16,658 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:35:16,659 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 22:35:16,659 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:35:16,659 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 22:35:16,660 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 22:35:16,660 INFO L87 Difference]: Start difference. First operand 62 states and 77 transitions. Second operand has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2024-11-09 22:35:16,711 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:35:16,711 INFO L93 Difference]: Finished difference Result 70 states and 84 transitions. [2024-11-09 22:35:16,711 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 22:35:16,711 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 59 [2024-11-09 22:35:16,712 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:35:16,712 INFO L225 Difference]: With dead ends: 70 [2024-11-09 22:35:16,712 INFO L226 Difference]: Without dead ends: 67 [2024-11-09 22:35:16,713 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 59 GetRequests, 55 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-09 22:35:16,714 INFO L432 NwaCegarLoop]: 40 mSDtfsCounter, 5 mSDsluCounter, 105 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 145 SdHoareTripleChecker+Invalid, 41 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-09 22:35:16,714 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 145 Invalid, 41 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 22:35:16,716 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2024-11-09 22:35:16,722 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 66. [2024-11-09 22:35:16,723 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 66 states, 41 states have (on average 1.0975609756097562) internal successors, (45), 44 states have internal predecessors, (45), 18 states have call successors, (18), 6 states have call predecessors, (18), 6 states have return successors, (17), 15 states have call predecessors, (17), 17 states have call successors, (17) [2024-11-09 22:35:16,723 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 66 states to 66 states and 80 transitions. [2024-11-09 22:35:16,723 INFO L78 Accepts]: Start accepts. Automaton has 66 states and 80 transitions. Word has length 59 [2024-11-09 22:35:16,723 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:35:16,724 INFO L471 AbstractCegarLoop]: Abstraction has 66 states and 80 transitions. [2024-11-09 22:35:16,724 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2024-11-09 22:35:16,724 INFO L276 IsEmpty]: Start isEmpty. Operand 66 states and 80 transitions. [2024-11-09 22:35:16,725 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2024-11-09 22:35:16,725 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:35:16,725 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 5, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:35:16,738 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-09 22:35:16,928 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:35:16,929 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:35:16,929 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:35:16,929 INFO L85 PathProgramCache]: Analyzing trace with hash -1573647644, now seen corresponding path program 1 times [2024-11-09 22:35:16,929 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:35:16,929 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1659901705] [2024-11-09 22:35:16,929 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:35:16,929 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:35:16,943 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:35:16,944 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1635253730] [2024-11-09 22:35:16,944 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:35:16,944 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:35:16,944 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:35:16,946 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:35:16,947 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-09 22:35:16,995 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:16,996 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 25 conjuncts are in the unsatisfiable core [2024-11-09 22:35:16,998 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:35:17,143 INFO L134 CoverageAnalysis]: Checked inductivity of 95 backedges. 13 proven. 7 refuted. 0 times theorem prover too weak. 75 trivial. 0 not checked. [2024-11-09 22:35:17,143 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:35:17,219 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:35:17,219 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1659901705] [2024-11-09 22:35:17,220 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:35:17,220 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1635253730] [2024-11-09 22:35:17,220 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1635253730] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 22:35:17,229 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-09 22:35:17,229 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2024-11-09 22:35:17,230 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [498539339] [2024-11-09 22:35:17,230 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-09 22:35:17,230 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-09 22:35:17,230 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:35:17,231 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-09 22:35:17,231 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=122, Unknown=0, NotChecked=0, Total=156 [2024-11-09 22:35:17,231 INFO L87 Difference]: Start difference. First operand 66 states and 80 transitions. Second operand has 10 states, 10 states have (on average 2.5) internal successors, (25), 8 states have internal predecessors, (25), 5 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2024-11-09 22:35:17,390 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:35:17,390 INFO L93 Difference]: Finished difference Result 100 states and 131 transitions. [2024-11-09 22:35:17,391 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-09 22:35:17,391 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.5) internal successors, (25), 8 states have internal predecessors, (25), 5 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) Word has length 67 [2024-11-09 22:35:17,392 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:35:17,393 INFO L225 Difference]: With dead ends: 100 [2024-11-09 22:35:17,393 INFO L226 Difference]: Without dead ends: 97 [2024-11-09 22:35:17,393 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 82 GetRequests, 69 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 22 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=47, Invalid=163, Unknown=0, NotChecked=0, Total=210 [2024-11-09 22:35:17,393 INFO L432 NwaCegarLoop]: 39 mSDtfsCounter, 21 mSDsluCounter, 197 mSDsCounter, 0 mSdLazyCounter, 149 mSolverCounterSat, 21 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 236 SdHoareTripleChecker+Invalid, 170 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 21 IncrementalHoareTripleChecker+Valid, 149 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 22:35:17,394 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 236 Invalid, 170 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [21 Valid, 149 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 22:35:17,394 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 97 states. [2024-11-09 22:35:17,410 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 97 to 84. [2024-11-09 22:35:17,410 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 84 states, 50 states have (on average 1.12) internal successors, (56), 53 states have internal predecessors, (56), 26 states have call successors, (26), 7 states have call predecessors, (26), 7 states have return successors, (25), 23 states have call predecessors, (25), 25 states have call successors, (25) [2024-11-09 22:35:17,413 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 84 states to 84 states and 107 transitions. [2024-11-09 22:35:17,413 INFO L78 Accepts]: Start accepts. Automaton has 84 states and 107 transitions. Word has length 67 [2024-11-09 22:35:17,414 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:35:17,414 INFO L471 AbstractCegarLoop]: Abstraction has 84 states and 107 transitions. [2024-11-09 22:35:17,415 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.5) internal successors, (25), 8 states have internal predecessors, (25), 5 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2024-11-09 22:35:17,415 INFO L276 IsEmpty]: Start isEmpty. Operand 84 states and 107 transitions. [2024-11-09 22:35:17,415 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2024-11-09 22:35:17,417 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:35:17,417 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 5, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:35:17,430 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-09 22:35:17,621 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:35:17,622 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:35:17,622 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:35:17,622 INFO L85 PathProgramCache]: Analyzing trace with hash -611527986, now seen corresponding path program 1 times [2024-11-09 22:35:17,622 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:35:17,622 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [744537434] [2024-11-09 22:35:17,622 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:35:17,622 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:35:17,635 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:17,749 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 22:35:17,750 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:17,751 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-09 22:35:17,752 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:17,756 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-09 22:35:17,758 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:17,774 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-09 22:35:17,775 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:17,777 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-09 22:35:17,778 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:17,780 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-09 22:35:17,785 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:17,787 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 39 [2024-11-09 22:35:17,788 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:17,791 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 44 [2024-11-09 22:35:17,792 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:17,794 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 49 [2024-11-09 22:35:17,795 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:17,797 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 54 [2024-11-09 22:35:17,798 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:17,800 INFO L134 CoverageAnalysis]: Checked inductivity of 95 backedges. 14 proven. 12 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2024-11-09 22:35:17,800 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:35:17,800 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [744537434] [2024-11-09 22:35:17,800 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [744537434] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 22:35:17,800 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1881788408] [2024-11-09 22:35:17,800 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:35:17,801 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:35:17,801 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:35:17,802 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:35:17,803 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-09 22:35:17,845 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:17,846 INFO L255 TraceCheckSpWp]: Trace formula consists of 171 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-09 22:35:17,848 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:35:17,889 INFO L134 CoverageAnalysis]: Checked inductivity of 95 backedges. 14 proven. 12 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2024-11-09 22:35:17,889 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:35:17,964 INFO L134 CoverageAnalysis]: Checked inductivity of 95 backedges. 14 proven. 12 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2024-11-09 22:35:17,964 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1881788408] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:35:17,964 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 22:35:17,964 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 12 [2024-11-09 22:35:17,964 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1551369610] [2024-11-09 22:35:17,965 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 22:35:17,965 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-09 22:35:17,965 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:35:17,965 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-09 22:35:17,965 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=103, Unknown=0, NotChecked=0, Total=132 [2024-11-09 22:35:17,966 INFO L87 Difference]: Start difference. First operand 84 states and 107 transitions. Second operand has 12 states, 12 states have (on average 3.3333333333333335) internal successors, (40), 11 states have internal predecessors, (40), 7 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2024-11-09 22:35:18,125 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:35:18,125 INFO L93 Difference]: Finished difference Result 138 states and 186 transitions. [2024-11-09 22:35:18,126 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-09 22:35:18,126 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 3.3333333333333335) internal successors, (40), 11 states have internal predecessors, (40), 7 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) Word has length 69 [2024-11-09 22:35:18,126 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:35:18,127 INFO L225 Difference]: With dead ends: 138 [2024-11-09 22:35:18,127 INFO L226 Difference]: Without dead ends: 129 [2024-11-09 22:35:18,128 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 166 GetRequests, 149 SyntacticMatches, 4 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 44 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=54, Invalid=156, Unknown=0, NotChecked=0, Total=210 [2024-11-09 22:35:18,128 INFO L432 NwaCegarLoop]: 49 mSDtfsCounter, 28 mSDsluCounter, 383 mSDsCounter, 0 mSdLazyCounter, 180 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 38 SdHoareTripleChecker+Valid, 432 SdHoareTripleChecker+Invalid, 195 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 180 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 22:35:18,128 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [38 Valid, 432 Invalid, 195 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 180 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 22:35:18,129 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 129 states. [2024-11-09 22:35:18,141 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 129 to 116. [2024-11-09 22:35:18,141 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 116 states, 69 states have (on average 1.144927536231884) internal successors, (79), 73 states have internal predecessors, (79), 39 states have call successors, (39), 7 states have call predecessors, (39), 7 states have return successors, (38), 35 states have call predecessors, (38), 38 states have call successors, (38) [2024-11-09 22:35:18,142 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 116 states to 116 states and 156 transitions. [2024-11-09 22:35:18,142 INFO L78 Accepts]: Start accepts. Automaton has 116 states and 156 transitions. Word has length 69 [2024-11-09 22:35:18,143 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:35:18,143 INFO L471 AbstractCegarLoop]: Abstraction has 116 states and 156 transitions. [2024-11-09 22:35:18,143 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 3.3333333333333335) internal successors, (40), 11 states have internal predecessors, (40), 7 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2024-11-09 22:35:18,143 INFO L276 IsEmpty]: Start isEmpty. Operand 116 states and 156 transitions. [2024-11-09 22:35:18,144 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 77 [2024-11-09 22:35:18,144 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:35:18,144 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 6, 5, 5, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:35:18,156 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-11-09 22:35:18,344 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:35:18,345 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:35:18,346 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:35:18,346 INFO L85 PathProgramCache]: Analyzing trace with hash -616299726, now seen corresponding path program 1 times [2024-11-09 22:35:18,346 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:35:18,346 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [245279131] [2024-11-09 22:35:18,346 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:35:18,346 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:35:18,365 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:35:18,365 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2139208345] [2024-11-09 22:35:18,366 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:35:18,366 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:35:18,366 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:35:18,368 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:35:18,369 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-09 22:35:18,413 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:18,414 INFO L255 TraceCheckSpWp]: Trace formula consists of 185 conjuncts, 23 conjuncts are in the unsatisfiable core [2024-11-09 22:35:18,416 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:35:18,683 INFO L134 CoverageAnalysis]: Checked inductivity of 117 backedges. 16 proven. 16 refuted. 0 times theorem prover too weak. 85 trivial. 0 not checked. [2024-11-09 22:35:18,683 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:35:18,867 INFO L134 CoverageAnalysis]: Checked inductivity of 117 backedges. 10 proven. 7 refuted. 0 times theorem prover too weak. 100 trivial. 0 not checked. [2024-11-09 22:35:18,867 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:35:18,867 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [245279131] [2024-11-09 22:35:18,867 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:35:18,867 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2139208345] [2024-11-09 22:35:18,867 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2139208345] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:35:18,867 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 22:35:18,867 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 8] total 15 [2024-11-09 22:35:18,867 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1023182453] [2024-11-09 22:35:18,868 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 22:35:18,868 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-09 22:35:18,868 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:35:18,868 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-09 22:35:18,868 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=43, Invalid=167, Unknown=0, NotChecked=0, Total=210 [2024-11-09 22:35:18,869 INFO L87 Difference]: Start difference. First operand 116 states and 156 transitions. Second operand has 15 states, 15 states have (on average 2.8) internal successors, (42), 13 states have internal predecessors, (42), 8 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 8 states have call predecessors, (20), 8 states have call successors, (20) [2024-11-09 22:35:19,594 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:35:19,594 INFO L93 Difference]: Finished difference Result 170 states and 233 transitions. [2024-11-09 22:35:19,595 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-09 22:35:19,595 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.8) internal successors, (42), 13 states have internal predecessors, (42), 8 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 8 states have call predecessors, (20), 8 states have call successors, (20) Word has length 76 [2024-11-09 22:35:19,595 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:35:19,596 INFO L225 Difference]: With dead ends: 170 [2024-11-09 22:35:19,596 INFO L226 Difference]: Without dead ends: 166 [2024-11-09 22:35:19,597 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 155 GetRequests, 135 SyntacticMatches, 2 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 48 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=85, Invalid=295, Unknown=0, NotChecked=0, Total=380 [2024-11-09 22:35:19,597 INFO L432 NwaCegarLoop]: 45 mSDtfsCounter, 48 mSDsluCounter, 283 mSDsCounter, 0 mSdLazyCounter, 209 mSolverCounterSat, 40 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 56 SdHoareTripleChecker+Valid, 328 SdHoareTripleChecker+Invalid, 249 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 40 IncrementalHoareTripleChecker+Valid, 209 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-09 22:35:19,597 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [56 Valid, 328 Invalid, 249 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [40 Valid, 209 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-09 22:35:19,598 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 166 states. [2024-11-09 22:35:19,628 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 166 to 163. [2024-11-09 22:35:19,628 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 163 states, 96 states have (on average 1.15625) internal successors, (111), 103 states have internal predecessors, (111), 58 states have call successors, (58), 8 states have call predecessors, (58), 8 states have return successors, (56), 51 states have call predecessors, (56), 56 states have call successors, (56) [2024-11-09 22:35:19,629 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 163 states to 163 states and 225 transitions. [2024-11-09 22:35:19,630 INFO L78 Accepts]: Start accepts. Automaton has 163 states and 225 transitions. Word has length 76 [2024-11-09 22:35:19,630 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:35:19,630 INFO L471 AbstractCegarLoop]: Abstraction has 163 states and 225 transitions. [2024-11-09 22:35:19,630 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.8) internal successors, (42), 13 states have internal predecessors, (42), 8 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 8 states have call predecessors, (20), 8 states have call successors, (20) [2024-11-09 22:35:19,630 INFO L276 IsEmpty]: Start isEmpty. Operand 163 states and 225 transitions. [2024-11-09 22:35:19,631 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 82 [2024-11-09 22:35:19,631 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:35:19,631 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:35:19,643 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-09 22:35:19,835 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:35:19,836 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:35:19,836 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:35:19,836 INFO L85 PathProgramCache]: Analyzing trace with hash 1530494997, now seen corresponding path program 2 times [2024-11-09 22:35:19,836 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:35:19,836 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [975744217] [2024-11-09 22:35:19,836 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:35:19,836 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:35:19,858 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:35:19,859 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [177212783] [2024-11-09 22:35:19,859 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-09 22:35:19,859 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:35:19,859 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:35:19,860 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:35:19,861 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-09 22:35:19,904 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-09 22:35:19,904 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 22:35:19,905 INFO L255 TraceCheckSpWp]: Trace formula consists of 194 conjuncts, 23 conjuncts are in the unsatisfiable core [2024-11-09 22:35:19,907 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:35:20,046 INFO L134 CoverageAnalysis]: Checked inductivity of 140 backedges. 12 proven. 8 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2024-11-09 22:35:20,046 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:35:20,104 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:35:20,104 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [975744217] [2024-11-09 22:35:20,104 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:35:20,104 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [177212783] [2024-11-09 22:35:20,105 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [177212783] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 22:35:20,105 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-09 22:35:20,105 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2024-11-09 22:35:20,105 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [687182628] [2024-11-09 22:35:20,105 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-09 22:35:20,105 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-09 22:35:20,105 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:35:20,106 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-09 22:35:20,106 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2024-11-09 22:35:20,106 INFO L87 Difference]: Start difference. First operand 163 states and 225 transitions. Second operand has 7 states, 7 states have (on average 3.7142857142857144) internal successors, (26), 6 states have internal predecessors, (26), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-11-09 22:35:20,212 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:35:20,212 INFO L93 Difference]: Finished difference Result 176 states and 236 transitions. [2024-11-09 22:35:20,212 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-09 22:35:20,212 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.7142857142857144) internal successors, (26), 6 states have internal predecessors, (26), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 81 [2024-11-09 22:35:20,212 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:35:20,214 INFO L225 Difference]: With dead ends: 176 [2024-11-09 22:35:20,215 INFO L226 Difference]: Without dead ends: 173 [2024-11-09 22:35:20,215 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 105 GetRequests, 94 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2024-11-09 22:35:20,216 INFO L432 NwaCegarLoop]: 48 mSDtfsCounter, 14 mSDsluCounter, 194 mSDsCounter, 0 mSdLazyCounter, 96 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 242 SdHoareTripleChecker+Invalid, 103 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 96 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 22:35:20,217 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [20 Valid, 242 Invalid, 103 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 96 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 22:35:20,217 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 173 states. [2024-11-09 22:35:20,237 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 173 to 171. [2024-11-09 22:35:20,238 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 171 states, 102 states have (on average 1.1470588235294117) internal successors, (117), 109 states have internal predecessors, (117), 58 states have call successors, (58), 10 states have call predecessors, (58), 10 states have return successors, (56), 51 states have call predecessors, (56), 56 states have call successors, (56) [2024-11-09 22:35:20,239 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 171 states to 171 states and 231 transitions. [2024-11-09 22:35:20,240 INFO L78 Accepts]: Start accepts. Automaton has 171 states and 231 transitions. Word has length 81 [2024-11-09 22:35:20,240 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:35:20,240 INFO L471 AbstractCegarLoop]: Abstraction has 171 states and 231 transitions. [2024-11-09 22:35:20,240 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 3.7142857142857144) internal successors, (26), 6 states have internal predecessors, (26), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-11-09 22:35:20,240 INFO L276 IsEmpty]: Start isEmpty. Operand 171 states and 231 transitions. [2024-11-09 22:35:20,241 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2024-11-09 22:35:20,241 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:35:20,241 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:35:20,257 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2024-11-09 22:35:20,445 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2024-11-09 22:35:20,446 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:35:20,446 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:35:20,446 INFO L85 PathProgramCache]: Analyzing trace with hash -1524123438, now seen corresponding path program 3 times [2024-11-09 22:35:20,446 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:35:20,446 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1408037674] [2024-11-09 22:35:20,447 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:35:20,447 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:35:20,461 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:35:20,462 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [578224725] [2024-11-09 22:35:20,462 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-09 22:35:20,462 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:35:20,462 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:35:20,464 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:35:20,466 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-09 22:35:20,513 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-09 22:35:20,513 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 22:35:20,514 INFO L255 TraceCheckSpWp]: Trace formula consists of 147 conjuncts, 49 conjuncts are in the unsatisfiable core [2024-11-09 22:35:20,516 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:35:21,087 INFO L134 CoverageAnalysis]: Checked inductivity of 167 backedges. 43 proven. 22 refuted. 0 times theorem prover too weak. 102 trivial. 0 not checked. [2024-11-09 22:35:21,087 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:35:22,173 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:35:22,173 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1408037674] [2024-11-09 22:35:22,173 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:35:22,173 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [578224725] [2024-11-09 22:35:22,173 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [578224725] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 22:35:22,173 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-09 22:35:22,173 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2024-11-09 22:35:22,173 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2038609166] [2024-11-09 22:35:22,173 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-09 22:35:22,173 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-09 22:35:22,174 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:35:22,174 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-09 22:35:22,174 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=394, Unknown=0, NotChecked=0, Total=462 [2024-11-09 22:35:22,174 INFO L87 Difference]: Start difference. First operand 171 states and 231 transitions. Second operand has 15 states, 14 states have (on average 2.2857142857142856) internal successors, (32), 14 states have internal predecessors, (32), 5 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2024-11-09 22:35:22,500 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:35:22,501 INFO L93 Difference]: Finished difference Result 180 states and 239 transitions. [2024-11-09 22:35:22,501 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-09 22:35:22,501 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 2.2857142857142856) internal successors, (32), 14 states have internal predecessors, (32), 5 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) Word has length 86 [2024-11-09 22:35:22,501 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:35:22,502 INFO L225 Difference]: With dead ends: 180 [2024-11-09 22:35:22,502 INFO L226 Difference]: Without dead ends: 177 [2024-11-09 22:35:22,502 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 116 GetRequests, 93 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 111 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=94, Invalid=506, Unknown=0, NotChecked=0, Total=600 [2024-11-09 22:35:22,503 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 28 mSDsluCounter, 315 mSDsCounter, 0 mSdLazyCounter, 364 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 38 SdHoareTripleChecker+Valid, 348 SdHoareTripleChecker+Invalid, 373 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 364 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-09 22:35:22,503 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [38 Valid, 348 Invalid, 373 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 364 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-09 22:35:22,503 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 177 states. [2024-11-09 22:35:22,518 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 177 to 175. [2024-11-09 22:35:22,518 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 175 states, 105 states have (on average 1.1428571428571428) internal successors, (120), 112 states have internal predecessors, (120), 58 states have call successors, (58), 11 states have call predecessors, (58), 11 states have return successors, (56), 51 states have call predecessors, (56), 56 states have call successors, (56) [2024-11-09 22:35:22,519 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 175 states to 175 states and 234 transitions. [2024-11-09 22:35:22,520 INFO L78 Accepts]: Start accepts. Automaton has 175 states and 234 transitions. Word has length 86 [2024-11-09 22:35:22,520 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:35:22,520 INFO L471 AbstractCegarLoop]: Abstraction has 175 states and 234 transitions. [2024-11-09 22:35:22,520 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 14 states have (on average 2.2857142857142856) internal successors, (32), 14 states have internal predecessors, (32), 5 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2024-11-09 22:35:22,520 INFO L276 IsEmpty]: Start isEmpty. Operand 175 states and 234 transitions. [2024-11-09 22:35:22,521 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2024-11-09 22:35:22,521 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:35:22,521 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 6, 6, 6, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:35:22,533 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2024-11-09 22:35:22,721 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-11-09 22:35:22,721 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:35:22,722 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:35:22,722 INFO L85 PathProgramCache]: Analyzing trace with hash -1563243110, now seen corresponding path program 2 times [2024-11-09 22:35:22,722 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:35:22,722 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [426991318] [2024-11-09 22:35:22,722 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:35:22,722 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:35:22,740 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:35:22,741 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1829768801] [2024-11-09 22:35:22,741 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-09 22:35:22,742 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:35:22,742 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:35:22,743 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:35:22,744 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-09 22:35:22,789 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-09 22:35:22,790 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 22:35:22,790 INFO L255 TraceCheckSpWp]: Trace formula consists of 204 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-11-09 22:35:22,792 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:35:22,868 INFO L134 CoverageAnalysis]: Checked inductivity of 201 backedges. 16 proven. 13 refuted. 0 times theorem prover too weak. 172 trivial. 0 not checked. [2024-11-09 22:35:22,869 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:35:22,945 INFO L134 CoverageAnalysis]: Checked inductivity of 201 backedges. 16 proven. 0 refuted. 0 times theorem prover too weak. 185 trivial. 0 not checked. [2024-11-09 22:35:22,945 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:35:22,945 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [426991318] [2024-11-09 22:35:22,945 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:35:22,945 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1829768801] [2024-11-09 22:35:22,945 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1829768801] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-09 22:35:22,945 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-09 22:35:22,945 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [7] total 8 [2024-11-09 22:35:22,946 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1613438484] [2024-11-09 22:35:22,946 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:35:22,946 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 22:35:22,946 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:35:22,946 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 22:35:22,946 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2024-11-09 22:35:22,947 INFO L87 Difference]: Start difference. First operand 175 states and 234 transitions. Second operand has 5 states, 5 states have (on average 4.0) internal successors, (20), 4 states have internal predecessors, (20), 2 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2024-11-09 22:35:22,989 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:35:22,989 INFO L93 Difference]: Finished difference Result 182 states and 240 transitions. [2024-11-09 22:35:22,990 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 22:35:22,990 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.0) internal successors, (20), 4 states have internal predecessors, (20), 2 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) Word has length 90 [2024-11-09 22:35:22,990 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:35:22,991 INFO L225 Difference]: With dead ends: 182 [2024-11-09 22:35:22,991 INFO L226 Difference]: Without dead ends: 179 [2024-11-09 22:35:22,992 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 179 GetRequests, 170 SyntacticMatches, 2 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=20, Invalid=52, Unknown=0, NotChecked=0, Total=72 [2024-11-09 22:35:22,992 INFO L432 NwaCegarLoop]: 39 mSDtfsCounter, 4 mSDsluCounter, 102 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 141 SdHoareTripleChecker+Invalid, 29 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-09 22:35:22,992 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 141 Invalid, 29 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 22:35:22,993 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 179 states. [2024-11-09 22:35:23,009 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 179 to 152. [2024-11-09 22:35:23,010 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 152 states, 93 states have (on average 1.1397849462365592) internal successors, (106), 97 states have internal predecessors, (106), 47 states have call successors, (47), 11 states have call predecessors, (47), 11 states have return successors, (45), 43 states have call predecessors, (45), 45 states have call successors, (45) [2024-11-09 22:35:23,010 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 152 states to 152 states and 198 transitions. [2024-11-09 22:35:23,011 INFO L78 Accepts]: Start accepts. Automaton has 152 states and 198 transitions. Word has length 90 [2024-11-09 22:35:23,011 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:35:23,011 INFO L471 AbstractCegarLoop]: Abstraction has 152 states and 198 transitions. [2024-11-09 22:35:23,011 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.0) internal successors, (20), 4 states have internal predecessors, (20), 2 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2024-11-09 22:35:23,011 INFO L276 IsEmpty]: Start isEmpty. Operand 152 states and 198 transitions. [2024-11-09 22:35:23,012 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2024-11-09 22:35:23,012 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:35:23,012 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:35:23,024 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2024-11-09 22:35:23,216 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2024-11-09 22:35:23,217 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:35:23,217 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:35:23,217 INFO L85 PathProgramCache]: Analyzing trace with hash 797294596, now seen corresponding path program 1 times [2024-11-09 22:35:23,217 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:35:23,217 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1389477638] [2024-11-09 22:35:23,217 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:35:23,217 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:35:23,228 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:35:23,229 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [899540820] [2024-11-09 22:35:23,229 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:35:23,229 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:35:23,229 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:35:23,230 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:35:23,231 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-09 22:35:23,276 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:23,277 INFO L255 TraceCheckSpWp]: Trace formula consists of 214 conjuncts, 41 conjuncts are in the unsatisfiable core [2024-11-09 22:35:23,278 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:35:23,683 INFO L134 CoverageAnalysis]: Checked inductivity of 198 backedges. 22 proven. 19 refuted. 0 times theorem prover too weak. 157 trivial. 0 not checked. [2024-11-09 22:35:23,683 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:35:24,353 INFO L134 CoverageAnalysis]: Checked inductivity of 198 backedges. 16 proven. 10 refuted. 0 times theorem prover too weak. 172 trivial. 0 not checked. [2024-11-09 22:35:24,353 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:35:24,354 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1389477638] [2024-11-09 22:35:24,354 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:35:24,354 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [899540820] [2024-11-09 22:35:24,354 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [899540820] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:35:24,354 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 22:35:24,354 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 21 [2024-11-09 22:35:24,354 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1790978089] [2024-11-09 22:35:24,354 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 22:35:24,354 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-09 22:35:24,354 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:35:24,355 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-09 22:35:24,355 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=356, Unknown=0, NotChecked=0, Total=420 [2024-11-09 22:35:24,355 INFO L87 Difference]: Start difference. First operand 152 states and 198 transitions. Second operand has 21 states, 19 states have (on average 2.4210526315789473) internal successors, (46), 18 states have internal predecessors, (46), 10 states have call successors, (27), 3 states have call predecessors, (27), 2 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) [2024-11-09 22:35:27,396 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:35:27,397 INFO L93 Difference]: Finished difference Result 263 states and 370 transitions. [2024-11-09 22:35:27,397 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2024-11-09 22:35:27,397 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 19 states have (on average 2.4210526315789473) internal successors, (46), 18 states have internal predecessors, (46), 10 states have call successors, (27), 3 states have call predecessors, (27), 2 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) Word has length 92 [2024-11-09 22:35:27,398 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:35:27,399 INFO L225 Difference]: With dead ends: 263 [2024-11-09 22:35:27,399 INFO L226 Difference]: Without dead ends: 258 [2024-11-09 22:35:27,399 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 199 GetRequests, 163 SyntacticMatches, 0 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 206 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=255, Invalid=1151, Unknown=0, NotChecked=0, Total=1406 [2024-11-09 22:35:27,400 INFO L432 NwaCegarLoop]: 53 mSDtfsCounter, 102 mSDsluCounter, 601 mSDsCounter, 0 mSdLazyCounter, 577 mSolverCounterSat, 113 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 107 SdHoareTripleChecker+Valid, 654 SdHoareTripleChecker+Invalid, 690 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 113 IncrementalHoareTripleChecker+Valid, 577 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.0s IncrementalHoareTripleChecker+Time [2024-11-09 22:35:27,400 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [107 Valid, 654 Invalid, 690 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [113 Valid, 577 Invalid, 0 Unknown, 0 Unchecked, 2.0s Time] [2024-11-09 22:35:27,400 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 258 states. [2024-11-09 22:35:27,460 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 258 to 255. [2024-11-09 22:35:27,461 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 255 states, 147 states have (on average 1.183673469387755) internal successors, (174), 150 states have internal predecessors, (174), 94 states have call successors, (94), 13 states have call predecessors, (94), 13 states have return successors, (92), 91 states have call predecessors, (92), 92 states have call successors, (92) [2024-11-09 22:35:27,462 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 255 states to 255 states and 360 transitions. [2024-11-09 22:35:27,462 INFO L78 Accepts]: Start accepts. Automaton has 255 states and 360 transitions. Word has length 92 [2024-11-09 22:35:27,463 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:35:27,464 INFO L471 AbstractCegarLoop]: Abstraction has 255 states and 360 transitions. [2024-11-09 22:35:27,464 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 19 states have (on average 2.4210526315789473) internal successors, (46), 18 states have internal predecessors, (46), 10 states have call successors, (27), 3 states have call predecessors, (27), 2 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) [2024-11-09 22:35:27,464 INFO L276 IsEmpty]: Start isEmpty. Operand 255 states and 360 transitions. [2024-11-09 22:35:27,465 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 104 [2024-11-09 22:35:27,465 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:35:27,465 INFO L215 NwaCegarLoop]: trace histogram [10, 9, 9, 6, 6, 6, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:35:27,477 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-11-09 22:35:27,669 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2024-11-09 22:35:27,670 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:35:27,670 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:35:27,670 INFO L85 PathProgramCache]: Analyzing trace with hash -1889884019, now seen corresponding path program 4 times [2024-11-09 22:35:27,670 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:35:27,670 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1086312977] [2024-11-09 22:35:27,670 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:35:27,670 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:35:27,683 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:27,751 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 22:35:27,751 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:27,752 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-09 22:35:27,753 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:27,753 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-09 22:35:27,754 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:27,754 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-09 22:35:27,755 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:27,756 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-09 22:35:27,756 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:27,757 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-09 22:35:27,757 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:27,758 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 39 [2024-11-09 22:35:27,758 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:27,759 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 44 [2024-11-09 22:35:27,759 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:27,760 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 49 [2024-11-09 22:35:27,760 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:27,761 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 54 [2024-11-09 22:35:27,762 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:27,762 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 66 [2024-11-09 22:35:27,763 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:27,764 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 71 [2024-11-09 22:35:27,765 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:27,766 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 76 [2024-11-09 22:35:27,767 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:27,768 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 81 [2024-11-09 22:35:27,769 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:27,770 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 93 [2024-11-09 22:35:27,771 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:27,772 INFO L134 CoverageAnalysis]: Checked inductivity of 247 backedges. 43 proven. 0 refuted. 0 times theorem prover too weak. 204 trivial. 0 not checked. [2024-11-09 22:35:27,772 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:35:27,772 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1086312977] [2024-11-09 22:35:27,772 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1086312977] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:35:27,772 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:35:27,772 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 22:35:27,773 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [692991731] [2024-11-09 22:35:27,773 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:35:27,773 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 22:35:27,773 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:35:27,773 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 22:35:27,773 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 22:35:27,774 INFO L87 Difference]: Start difference. First operand 255 states and 360 transitions. Second operand has 5 states, 5 states have (on average 6.6) internal successors, (33), 5 states have internal predecessors, (33), 3 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (15), 3 states have call predecessors, (15), 3 states have call successors, (15) [2024-11-09 22:35:27,859 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:35:27,860 INFO L93 Difference]: Finished difference Result 321 states and 448 transitions. [2024-11-09 22:35:27,860 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-09 22:35:27,860 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 6.6) internal successors, (33), 5 states have internal predecessors, (33), 3 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (15), 3 states have call predecessors, (15), 3 states have call successors, (15) Word has length 103 [2024-11-09 22:35:27,860 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:35:27,862 INFO L225 Difference]: With dead ends: 321 [2024-11-09 22:35:27,862 INFO L226 Difference]: Without dead ends: 230 [2024-11-09 22:35:27,862 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 37 GetRequests, 32 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2024-11-09 22:35:27,863 INFO L432 NwaCegarLoop]: 55 mSDtfsCounter, 8 mSDsluCounter, 134 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 189 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-09 22:35:27,863 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 189 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 22:35:27,863 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 230 states. [2024-11-09 22:35:27,911 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 230 to 215. [2024-11-09 22:35:27,912 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 215 states, 123 states have (on average 1.1382113821138211) internal successors, (140), 126 states have internal predecessors, (140), 78 states have call successors, (78), 13 states have call predecessors, (78), 13 states have return successors, (76), 75 states have call predecessors, (76), 76 states have call successors, (76) [2024-11-09 22:35:27,912 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 215 states to 215 states and 294 transitions. [2024-11-09 22:35:27,913 INFO L78 Accepts]: Start accepts. Automaton has 215 states and 294 transitions. Word has length 103 [2024-11-09 22:35:27,913 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:35:27,913 INFO L471 AbstractCegarLoop]: Abstraction has 215 states and 294 transitions. [2024-11-09 22:35:27,913 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 6.6) internal successors, (33), 5 states have internal predecessors, (33), 3 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (15), 3 states have call predecessors, (15), 3 states have call successors, (15) [2024-11-09 22:35:27,913 INFO L276 IsEmpty]: Start isEmpty. Operand 215 states and 294 transitions. [2024-11-09 22:35:27,915 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 110 [2024-11-09 22:35:27,915 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:35:27,915 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 6, 6, 6, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:35:27,916 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12 [2024-11-09 22:35:27,916 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:35:27,916 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:35:27,916 INFO L85 PathProgramCache]: Analyzing trace with hash 1162616412, now seen corresponding path program 1 times [2024-11-09 22:35:27,916 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:35:27,916 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [188674299] [2024-11-09 22:35:27,916 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:35:27,916 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:35:27,930 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:35:27,931 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1018384870] [2024-11-09 22:35:27,931 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:35:27,933 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:35:27,933 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:35:27,935 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:35:27,936 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-09 22:35:27,991 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:27,997 INFO L255 TraceCheckSpWp]: Trace formula consists of 246 conjuncts, 46 conjuncts are in the unsatisfiable core [2024-11-09 22:35:27,999 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:35:29,029 INFO L134 CoverageAnalysis]: Checked inductivity of 324 backedges. 57 proven. 32 refuted. 0 times theorem prover too weak. 235 trivial. 0 not checked. [2024-11-09 22:35:29,030 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:35:30,309 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:35:30,310 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [188674299] [2024-11-09 22:35:30,310 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:35:30,310 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1018384870] [2024-11-09 22:35:30,310 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1018384870] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 22:35:30,310 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-09 22:35:30,310 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2024-11-09 22:35:30,310 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [328955241] [2024-11-09 22:35:30,310 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-09 22:35:30,311 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-09 22:35:30,311 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:35:30,311 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-09 22:35:30,311 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=94, Invalid=412, Unknown=0, NotChecked=0, Total=506 [2024-11-09 22:35:30,311 INFO L87 Difference]: Start difference. First operand 215 states and 294 transitions. Second operand has 16 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 13 states have internal predecessors, (35), 7 states have call successors, (18), 2 states have call predecessors, (18), 3 states have return successors, (17), 7 states have call predecessors, (17), 6 states have call successors, (17) [2024-11-09 22:35:31,009 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:35:31,009 INFO L93 Difference]: Finished difference Result 228 states and 305 transitions. [2024-11-09 22:35:31,010 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-11-09 22:35:31,010 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 13 states have internal predecessors, (35), 7 states have call successors, (18), 2 states have call predecessors, (18), 3 states have return successors, (17), 7 states have call predecessors, (17), 6 states have call successors, (17) Word has length 109 [2024-11-09 22:35:31,010 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:35:31,011 INFO L225 Difference]: With dead ends: 228 [2024-11-09 22:35:31,011 INFO L226 Difference]: Without dead ends: 225 [2024-11-09 22:35:31,011 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 140 GetRequests, 115 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 128 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=134, Invalid=568, Unknown=0, NotChecked=0, Total=702 [2024-11-09 22:35:31,012 INFO L432 NwaCegarLoop]: 46 mSDtfsCounter, 33 mSDsluCounter, 400 mSDsCounter, 0 mSdLazyCounter, 503 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 45 SdHoareTripleChecker+Valid, 446 SdHoareTripleChecker+Invalid, 525 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 503 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-11-09 22:35:31,012 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [45 Valid, 446 Invalid, 525 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 503 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-11-09 22:35:31,012 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 225 states. [2024-11-09 22:35:31,054 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 225 to 223. [2024-11-09 22:35:31,055 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 223 states, 129 states have (on average 1.1317829457364341) internal successors, (146), 132 states have internal predecessors, (146), 78 states have call successors, (78), 15 states have call predecessors, (78), 15 states have return successors, (76), 75 states have call predecessors, (76), 76 states have call successors, (76) [2024-11-09 22:35:31,056 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 223 states to 223 states and 300 transitions. [2024-11-09 22:35:31,057 INFO L78 Accepts]: Start accepts. Automaton has 223 states and 300 transitions. Word has length 109 [2024-11-09 22:35:31,057 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:35:31,057 INFO L471 AbstractCegarLoop]: Abstraction has 223 states and 300 transitions. [2024-11-09 22:35:31,057 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 13 states have internal predecessors, (35), 7 states have call successors, (18), 2 states have call predecessors, (18), 3 states have return successors, (17), 7 states have call predecessors, (17), 6 states have call successors, (17) [2024-11-09 22:35:31,057 INFO L276 IsEmpty]: Start isEmpty. Operand 223 states and 300 transitions. [2024-11-09 22:35:31,059 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 125 [2024-11-09 22:35:31,059 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:35:31,059 INFO L215 NwaCegarLoop]: trace histogram [14, 13, 13, 6, 6, 6, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:35:31,077 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2024-11-09 22:35:31,263 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2024-11-09 22:35:31,264 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:35:31,264 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:35:31,264 INFO L85 PathProgramCache]: Analyzing trace with hash -1963907256, now seen corresponding path program 1 times [2024-11-09 22:35:31,264 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:35:31,264 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [788837817] [2024-11-09 22:35:31,264 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:35:31,264 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:35:31,273 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:31,338 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 22:35:31,339 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:31,340 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-09 22:35:31,341 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:31,341 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-09 22:35:31,342 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:31,342 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-09 22:35:31,343 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:31,343 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-09 22:35:31,343 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:31,344 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-09 22:35:31,344 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:31,345 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 39 [2024-11-09 22:35:31,345 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:31,346 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 44 [2024-11-09 22:35:31,346 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:31,347 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 49 [2024-11-09 22:35:31,348 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:31,348 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 54 [2024-11-09 22:35:31,349 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:31,349 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 66 [2024-11-09 22:35:31,350 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:31,351 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 71 [2024-11-09 22:35:31,352 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:31,353 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 76 [2024-11-09 22:35:31,354 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:31,355 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 81 [2024-11-09 22:35:31,356 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:31,357 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 89 [2024-11-09 22:35:31,358 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:31,359 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 94 [2024-11-09 22:35:31,360 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:31,361 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 99 [2024-11-09 22:35:31,361 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:31,362 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 104 [2024-11-09 22:35:31,363 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:31,364 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 114 [2024-11-09 22:35:31,365 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:31,367 INFO L134 CoverageAnalysis]: Checked inductivity of 429 backedges. 46 proven. 11 refuted. 0 times theorem prover too weak. 372 trivial. 0 not checked. [2024-11-09 22:35:31,367 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:35:31,367 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [788837817] [2024-11-09 22:35:31,367 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [788837817] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 22:35:31,367 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [791562066] [2024-11-09 22:35:31,367 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:35:31,367 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:35:31,368 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:35:31,369 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:35:31,370 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-11-09 22:35:31,423 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:35:31,425 INFO L255 TraceCheckSpWp]: Trace formula consists of 281 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 22:35:31,426 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:35:31,452 INFO L134 CoverageAnalysis]: Checked inductivity of 429 backedges. 92 proven. 11 refuted. 0 times theorem prover too weak. 326 trivial. 0 not checked. [2024-11-09 22:35:31,452 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:35:31,535 INFO L134 CoverageAnalysis]: Checked inductivity of 429 backedges. 46 proven. 11 refuted. 0 times theorem prover too weak. 372 trivial. 0 not checked. [2024-11-09 22:35:31,536 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [791562066] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:35:31,536 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 22:35:31,536 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 7 [2024-11-09 22:35:31,536 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [332268838] [2024-11-09 22:35:31,536 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 22:35:31,537 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-09 22:35:31,537 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:35:31,537 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-09 22:35:31,537 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2024-11-09 22:35:31,537 INFO L87 Difference]: Start difference. First operand 223 states and 300 transitions. Second operand has 7 states, 7 states have (on average 5.142857142857143) internal successors, (36), 7 states have internal predecessors, (36), 4 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 4 states have call predecessors, (20), 4 states have call successors, (20) [2024-11-09 22:35:31,721 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:35:31,722 INFO L93 Difference]: Finished difference Result 257 states and 346 transitions. [2024-11-09 22:35:31,722 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-09 22:35:31,722 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 5.142857142857143) internal successors, (36), 7 states have internal predecessors, (36), 4 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 4 states have call predecessors, (20), 4 states have call successors, (20) Word has length 124 [2024-11-09 22:35:31,722 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:35:31,723 INFO L225 Difference]: With dead ends: 257 [2024-11-09 22:35:31,723 INFO L226 Difference]: Without dead ends: 244 [2024-11-09 22:35:31,724 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 302 GetRequests, 283 SyntacticMatches, 6 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=62, Invalid=148, Unknown=0, NotChecked=0, Total=210 [2024-11-09 22:35:31,724 INFO L432 NwaCegarLoop]: 77 mSDtfsCounter, 23 mSDsluCounter, 287 mSDsCounter, 0 mSdLazyCounter, 98 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 364 SdHoareTripleChecker+Invalid, 120 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 98 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 22:35:31,724 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 364 Invalid, 120 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 98 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 22:35:31,725 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 244 states. [2024-11-09 22:35:31,766 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 244 to 222. [2024-11-09 22:35:31,766 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 222 states, 129 states have (on average 1.124031007751938) internal successors, (145), 131 states have internal predecessors, (145), 77 states have call successors, (77), 15 states have call predecessors, (77), 15 states have return successors, (75), 75 states have call predecessors, (75), 75 states have call successors, (75) [2024-11-09 22:35:31,767 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 222 states to 222 states and 297 transitions. [2024-11-09 22:35:31,767 INFO L78 Accepts]: Start accepts. Automaton has 222 states and 297 transitions. Word has length 124 [2024-11-09 22:35:31,768 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:35:31,768 INFO L471 AbstractCegarLoop]: Abstraction has 222 states and 297 transitions. [2024-11-09 22:35:31,768 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 5.142857142857143) internal successors, (36), 7 states have internal predecessors, (36), 4 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 4 states have call predecessors, (20), 4 states have call successors, (20) [2024-11-09 22:35:31,768 INFO L276 IsEmpty]: Start isEmpty. Operand 222 states and 297 transitions. [2024-11-09 22:35:31,769 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 127 [2024-11-09 22:35:31,769 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:35:31,769 INFO L215 NwaCegarLoop]: trace histogram [14, 13, 13, 6, 6, 6, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:35:31,781 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2024-11-09 22:35:31,969 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2024-11-09 22:35:31,969 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:35:31,970 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:35:31,970 INFO L85 PathProgramCache]: Analyzing trace with hash -1457294975, now seen corresponding path program 2 times [2024-11-09 22:35:31,970 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:35:31,970 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [20061211] [2024-11-09 22:35:31,970 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:35:31,970 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:35:31,984 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:35:31,984 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1543540389] [2024-11-09 22:35:31,984 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-09 22:35:31,984 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:35:31,985 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:35:31,986 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:35:31,987 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2024-11-09 22:35:32,056 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-09 22:35:32,057 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 22:35:32,059 INFO L255 TraceCheckSpWp]: Trace formula consists of 286 conjuncts, 52 conjuncts are in the unsatisfiable core [2024-11-09 22:35:32,061 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:35:32,514 INFO L134 CoverageAnalysis]: Checked inductivity of 441 backedges. 61 proven. 59 refuted. 0 times theorem prover too weak. 321 trivial. 0 not checked. [2024-11-09 22:35:32,514 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:35:32,692 INFO L134 CoverageAnalysis]: Checked inductivity of 441 backedges. 78 proven. 7 refuted. 0 times theorem prover too weak. 356 trivial. 0 not checked. [2024-11-09 22:35:32,692 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:35:32,692 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [20061211] [2024-11-09 22:35:32,692 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:35:32,692 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1543540389] [2024-11-09 22:35:32,692 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1543540389] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:35:32,692 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 22:35:32,692 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 8] total 22 [2024-11-09 22:35:32,692 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [903309952] [2024-11-09 22:35:32,692 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 22:35:32,693 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-11-09 22:35:32,693 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:35:32,693 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-09 22:35:32,693 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=395, Unknown=0, NotChecked=0, Total=462 [2024-11-09 22:35:32,694 INFO L87 Difference]: Start difference. First operand 222 states and 297 transitions. Second operand has 22 states, 22 states have (on average 2.8181818181818183) internal successors, (62), 19 states have internal predecessors, (62), 9 states have call successors, (30), 3 states have call predecessors, (30), 3 states have return successors, (30), 9 states have call predecessors, (30), 9 states have call successors, (30) [2024-11-09 22:35:34,646 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:35:34,646 INFO L93 Difference]: Finished difference Result 257 states and 345 transitions. [2024-11-09 22:35:34,646 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2024-11-09 22:35:34,647 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 2.8181818181818183) internal successors, (62), 19 states have internal predecessors, (62), 9 states have call successors, (30), 3 states have call predecessors, (30), 3 states have return successors, (30), 9 states have call predecessors, (30), 9 states have call successors, (30) Word has length 126 [2024-11-09 22:35:34,647 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:35:34,648 INFO L225 Difference]: With dead ends: 257 [2024-11-09 22:35:34,648 INFO L226 Difference]: Without dead ends: 253 [2024-11-09 22:35:34,648 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 262 GetRequests, 231 SyntacticMatches, 0 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 182 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=174, Invalid=882, Unknown=0, NotChecked=0, Total=1056 [2024-11-09 22:35:34,649 INFO L432 NwaCegarLoop]: 52 mSDtfsCounter, 70 mSDsluCounter, 602 mSDsCounter, 0 mSdLazyCounter, 717 mSolverCounterSat, 82 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 72 SdHoareTripleChecker+Valid, 654 SdHoareTripleChecker+Invalid, 799 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 82 IncrementalHoareTripleChecker+Valid, 717 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2024-11-09 22:35:34,649 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [72 Valid, 654 Invalid, 799 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [82 Valid, 717 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2024-11-09 22:35:34,649 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 253 states. [2024-11-09 22:35:34,702 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 253 to 224. [2024-11-09 22:35:34,703 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 224 states, 132 states have (on average 1.121212121212121) internal successors, (148), 133 states have internal predecessors, (148), 75 states have call successors, (75), 16 states have call predecessors, (75), 16 states have return successors, (74), 74 states have call predecessors, (74), 74 states have call successors, (74) [2024-11-09 22:35:34,703 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 224 states to 224 states and 297 transitions. [2024-11-09 22:35:34,704 INFO L78 Accepts]: Start accepts. Automaton has 224 states and 297 transitions. Word has length 126 [2024-11-09 22:35:34,704 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:35:34,704 INFO L471 AbstractCegarLoop]: Abstraction has 224 states and 297 transitions. [2024-11-09 22:35:34,704 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 2.8181818181818183) internal successors, (62), 19 states have internal predecessors, (62), 9 states have call successors, (30), 3 states have call predecessors, (30), 3 states have return successors, (30), 9 states have call predecessors, (30), 9 states have call successors, (30) [2024-11-09 22:35:34,704 INFO L276 IsEmpty]: Start isEmpty. Operand 224 states and 297 transitions. [2024-11-09 22:35:34,705 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 128 [2024-11-09 22:35:34,705 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:35:34,705 INFO L215 NwaCegarLoop]: trace histogram [15, 14, 14, 6, 6, 6, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:35:34,718 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2024-11-09 22:35:34,909 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:35:34,909 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:35:34,910 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:35:34,910 INFO L85 PathProgramCache]: Analyzing trace with hash -1922555051, now seen corresponding path program 3 times [2024-11-09 22:35:34,910 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:35:34,910 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [919189347] [2024-11-09 22:35:34,910 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:35:34,910 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:35:34,926 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:35:34,927 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [644548390] [2024-11-09 22:35:34,927 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-09 22:35:34,928 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:35:34,928 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:35:34,929 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:35:34,930 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2024-11-09 22:35:34,998 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2024-11-09 22:35:34,998 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 22:35:35,000 INFO L255 TraceCheckSpWp]: Trace formula consists of 206 conjuncts, 43 conjuncts are in the unsatisfiable core [2024-11-09 22:35:35,002 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:35:35,465 INFO L134 CoverageAnalysis]: Checked inductivity of 491 backedges. 37 proven. 45 refuted. 0 times theorem prover too weak. 409 trivial. 0 not checked. [2024-11-09 22:35:35,466 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:35:36,396 INFO L134 CoverageAnalysis]: Checked inductivity of 491 backedges. 28 proven. 39 refuted. 0 times theorem prover too weak. 424 trivial. 0 not checked. [2024-11-09 22:35:36,397 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:35:36,397 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [919189347] [2024-11-09 22:35:36,397 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:35:36,397 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [644548390] [2024-11-09 22:35:36,397 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [644548390] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:35:36,397 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 22:35:36,397 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 21 [2024-11-09 22:35:36,397 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1741126529] [2024-11-09 22:35:36,397 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 22:35:36,397 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-09 22:35:36,397 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:35:36,398 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-09 22:35:36,398 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=352, Unknown=0, NotChecked=0, Total=420 [2024-11-09 22:35:36,398 INFO L87 Difference]: Start difference. First operand 224 states and 297 transitions. Second operand has 21 states, 21 states have (on average 2.6666666666666665) internal successors, (56), 18 states have internal predecessors, (56), 11 states have call successors, (38), 3 states have call predecessors, (38), 2 states have return successors, (37), 12 states have call predecessors, (37), 11 states have call successors, (37) [2024-11-09 22:35:40,111 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:35:40,111 INFO L93 Difference]: Finished difference Result 329 states and 453 transitions. [2024-11-09 22:35:40,111 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2024-11-09 22:35:40,112 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 2.6666666666666665) internal successors, (56), 18 states have internal predecessors, (56), 11 states have call successors, (38), 3 states have call predecessors, (38), 2 states have return successors, (37), 12 states have call predecessors, (37), 11 states have call successors, (37) Word has length 127 [2024-11-09 22:35:40,112 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:35:40,113 INFO L225 Difference]: With dead ends: 329 [2024-11-09 22:35:40,113 INFO L226 Difference]: Without dead ends: 326 [2024-11-09 22:35:40,114 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 271 GetRequests, 233 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 222 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=305, Invalid=1255, Unknown=0, NotChecked=0, Total=1560 [2024-11-09 22:35:40,114 INFO L432 NwaCegarLoop]: 68 mSDtfsCounter, 88 mSDsluCounter, 759 mSDsCounter, 0 mSdLazyCounter, 721 mSolverCounterSat, 86 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 92 SdHoareTripleChecker+Valid, 827 SdHoareTripleChecker+Invalid, 807 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 86 IncrementalHoareTripleChecker+Valid, 721 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.9s IncrementalHoareTripleChecker+Time [2024-11-09 22:35:40,114 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [92 Valid, 827 Invalid, 807 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [86 Valid, 721 Invalid, 0 Unknown, 0 Unchecked, 1.9s Time] [2024-11-09 22:35:40,115 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 326 states. [2024-11-09 22:35:40,214 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 326 to 289. [2024-11-09 22:35:40,214 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 289 states, 166 states have (on average 1.1385542168674698) internal successors, (189), 167 states have internal predecessors, (189), 103 states have call successors, (103), 19 states have call predecessors, (103), 19 states have return successors, (102), 102 states have call predecessors, (102), 102 states have call successors, (102) [2024-11-09 22:35:40,216 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 289 states to 289 states and 394 transitions. [2024-11-09 22:35:40,216 INFO L78 Accepts]: Start accepts. Automaton has 289 states and 394 transitions. Word has length 127 [2024-11-09 22:35:40,216 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:35:40,216 INFO L471 AbstractCegarLoop]: Abstraction has 289 states and 394 transitions. [2024-11-09 22:35:40,216 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 2.6666666666666665) internal successors, (56), 18 states have internal predecessors, (56), 11 states have call successors, (38), 3 states have call predecessors, (38), 2 states have return successors, (37), 12 states have call predecessors, (37), 11 states have call successors, (37) [2024-11-09 22:35:40,217 INFO L276 IsEmpty]: Start isEmpty. Operand 289 states and 394 transitions. [2024-11-09 22:35:40,217 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 132 [2024-11-09 22:35:40,217 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:35:40,217 INFO L215 NwaCegarLoop]: trace histogram [15, 14, 14, 6, 6, 6, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:35:40,229 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2024-11-09 22:35:40,421 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2024-11-09 22:35:40,421 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:35:40,422 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:35:40,422 INFO L85 PathProgramCache]: Analyzing trace with hash -1667388634, now seen corresponding path program 4 times [2024-11-09 22:35:40,422 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:35:40,422 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1249393221] [2024-11-09 22:35:40,422 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:35:40,422 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:35:40,435 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:35:40,436 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1254847716] [2024-11-09 22:35:40,436 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-09 22:35:40,436 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:35:40,436 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:35:40,437 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:35:40,438 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2024-11-09 22:35:40,498 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-09 22:35:40,498 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 22:35:40,499 INFO L255 TraceCheckSpWp]: Trace formula consists of 256 conjuncts, 39 conjuncts are in the unsatisfiable core [2024-11-09 22:35:40,501 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:35:42,467 INFO L134 CoverageAnalysis]: Checked inductivity of 498 backedges. 57 proven. 56 refuted. 0 times theorem prover too weak. 385 trivial. 0 not checked. [2024-11-09 22:35:42,467 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:35:43,511 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:35:43,511 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1249393221] [2024-11-09 22:35:43,511 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:35:43,511 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1254847716] [2024-11-09 22:35:43,512 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1254847716] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 22:35:43,512 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-09 22:35:43,512 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2024-11-09 22:35:43,512 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1214706857] [2024-11-09 22:35:43,513 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-09 22:35:43,513 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-09 22:35:43,513 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:35:43,514 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-09 22:35:43,514 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=289, Unknown=0, NotChecked=0, Total=342 [2024-11-09 22:35:43,514 INFO L87 Difference]: Start difference. First operand 289 states and 394 transitions. Second operand has 15 states, 15 states have (on average 2.6) internal successors, (39), 13 states have internal predecessors, (39), 7 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) [2024-11-09 22:35:44,945 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:35:44,945 INFO L93 Difference]: Finished difference Result 341 states and 455 transitions. [2024-11-09 22:35:44,947 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-09 22:35:44,948 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.6) internal successors, (39), 13 states have internal predecessors, (39), 7 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) Word has length 131 [2024-11-09 22:35:44,948 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:35:44,949 INFO L225 Difference]: With dead ends: 341 [2024-11-09 22:35:44,949 INFO L226 Difference]: Without dead ends: 338 [2024-11-09 22:35:44,949 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 165 GetRequests, 139 SyntacticMatches, 2 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 71 ImplicationChecksByTransitivity, 2.2s TimeCoverageRelationStatistics Valid=105, Invalid=545, Unknown=0, NotChecked=0, Total=650 [2024-11-09 22:35:44,950 INFO L432 NwaCegarLoop]: 56 mSDtfsCounter, 29 mSDsluCounter, 467 mSDsCounter, 0 mSdLazyCounter, 399 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 523 SdHoareTripleChecker+Invalid, 425 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 399 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2024-11-09 22:35:44,950 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [39 Valid, 523 Invalid, 425 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 399 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2024-11-09 22:35:44,950 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 338 states. [2024-11-09 22:35:45,057 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 338 to 334. [2024-11-09 22:35:45,058 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 334 states, 194 states have (on average 1.1288659793814433) internal successors, (219), 195 states have internal predecessors, (219), 115 states have call successors, (115), 24 states have call predecessors, (115), 24 states have return successors, (114), 114 states have call predecessors, (114), 114 states have call successors, (114) [2024-11-09 22:35:45,059 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 334 states to 334 states and 448 transitions. [2024-11-09 22:35:45,059 INFO L78 Accepts]: Start accepts. Automaton has 334 states and 448 transitions. Word has length 131 [2024-11-09 22:35:45,059 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:35:45,059 INFO L471 AbstractCegarLoop]: Abstraction has 334 states and 448 transitions. [2024-11-09 22:35:45,060 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.6) internal successors, (39), 13 states have internal predecessors, (39), 7 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) [2024-11-09 22:35:45,060 INFO L276 IsEmpty]: Start isEmpty. Operand 334 states and 448 transitions. [2024-11-09 22:35:45,060 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 133 [2024-11-09 22:35:45,060 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:35:45,060 INFO L215 NwaCegarLoop]: trace histogram [16, 15, 15, 6, 6, 6, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:35:45,073 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2024-11-09 22:35:45,261 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2024-11-09 22:35:45,261 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:35:45,261 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:35:45,261 INFO L85 PathProgramCache]: Analyzing trace with hash 853351826, now seen corresponding path program 5 times [2024-11-09 22:35:45,261 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:35:45,261 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [776655098] [2024-11-09 22:35:45,261 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:35:45,261 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:35:45,279 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:35:45,281 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1349621846] [2024-11-09 22:35:45,281 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-09 22:35:45,281 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:35:45,281 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:35:45,282 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:35:45,283 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2024-11-09 22:35:45,407 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 7 check-sat command(s) [2024-11-09 22:35:45,407 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 22:35:45,408 INFO L255 TraceCheckSpWp]: Trace formula consists of 289 conjuncts, 48 conjuncts are in the unsatisfiable core [2024-11-09 22:35:45,410 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:35:46,110 INFO L134 CoverageAnalysis]: Checked inductivity of 552 backedges. 71 proven. 43 refuted. 0 times theorem prover too weak. 438 trivial. 0 not checked. [2024-11-09 22:35:46,110 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:35:51,205 INFO L134 CoverageAnalysis]: Checked inductivity of 552 backedges. 71 proven. 43 refuted. 0 times theorem prover too weak. 438 trivial. 0 not checked. [2024-11-09 22:35:51,205 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:35:51,205 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [776655098] [2024-11-09 22:35:51,205 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:35:51,205 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1349621846] [2024-11-09 22:35:51,205 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1349621846] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:35:51,205 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 22:35:51,205 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 23 [2024-11-09 22:35:51,206 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1842785505] [2024-11-09 22:35:51,206 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 22:35:51,206 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-11-09 22:35:51,206 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:35:51,206 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-09 22:35:51,206 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=108, Invalid=398, Unknown=0, NotChecked=0, Total=506 [2024-11-09 22:35:51,207 INFO L87 Difference]: Start difference. First operand 334 states and 448 transitions. Second operand has 23 states, 22 states have (on average 2.6363636363636362) internal successors, (58), 21 states have internal predecessors, (58), 12 states have call successors, (40), 3 states have call predecessors, (40), 2 states have return successors, (38), 12 states have call predecessors, (38), 11 states have call successors, (38) [2024-11-09 22:36:11,450 WARN L286 SmtUtils]: Spent 19.43s on a formula simplification that was a NOOP. DAG size: 94 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 22:36:19,954 WARN L286 SmtUtils]: Spent 8.12s on a formula simplification that was a NOOP. DAG size: 71 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 22:36:24,033 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:36:31,284 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:36:42,650 WARN L286 SmtUtils]: Spent 6.91s on a formula simplification that was a NOOP. DAG size: 69 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 22:36:46,717 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:36:54,262 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:36:55,725 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.46s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers []