./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/hard-ll_unwindbound5.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 803cd42f Calling Ultimate with: /root/.sdkman/candidates/java/current/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/hard-ll_unwindbound5.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 1eba5bc7e50ef659abfe155713ae512eb1ae4032ecb78db63a02f9acbcdf9dbe --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.dk.eval-assert-order-craig-803cd42-m [2024-11-22 01:28:51,552 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-22 01:28:51,629 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-22 01:28:51,636 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-22 01:28:51,638 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-22 01:28:51,674 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-22 01:28:51,675 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-22 01:28:51,676 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-22 01:28:51,676 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-22 01:28:51,676 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-22 01:28:51,677 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-22 01:28:51,677 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-22 01:28:51,678 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-22 01:28:51,678 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-22 01:28:51,678 INFO L153 SettingsManager]: * Use SBE=true [2024-11-22 01:28:51,679 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-22 01:28:51,679 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-22 01:28:51,681 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-22 01:28:51,681 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-22 01:28:51,681 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-22 01:28:51,682 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-22 01:28:51,684 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-22 01:28:51,684 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-22 01:28:51,685 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-22 01:28:51,687 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-22 01:28:51,687 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-22 01:28:51,688 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-22 01:28:51,688 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-22 01:28:51,688 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-22 01:28:51,688 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-22 01:28:51,689 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-22 01:28:51,689 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-22 01:28:51,691 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-22 01:28:51,692 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-22 01:28:51,692 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-22 01:28:51,692 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-22 01:28:51,693 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-22 01:28:51,693 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-22 01:28:51,693 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-22 01:28:51,693 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-22 01:28:51,694 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-22 01:28:51,695 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-22 01:28:51,695 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 -> 1eba5bc7e50ef659abfe155713ae512eb1ae4032ecb78db63a02f9acbcdf9dbe [2024-11-22 01:28:51,962 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-22 01:28:51,988 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-22 01:28:51,992 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-22 01:28:51,993 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-22 01:28:51,994 INFO L274 PluginConnector]: CDTParser initialized [2024-11-22 01:28:51,995 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/hard-ll_unwindbound5.c [2024-11-22 01:28:53,453 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-22 01:28:53,646 INFO L384 CDTParser]: Found 1 translation units. [2024-11-22 01:28:53,647 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/hard-ll_unwindbound5.c [2024-11-22 01:28:53,655 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/7fa9afa99/419c1d9e94c54480bd218dec585fd8a8/FLAG013ef0842 [2024-11-22 01:28:53,669 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/7fa9afa99/419c1d9e94c54480bd218dec585fd8a8 [2024-11-22 01:28:53,672 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-22 01:28:53,673 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-22 01:28:53,674 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-22 01:28:53,674 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-22 01:28:53,680 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-22 01:28:53,681 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 22.11 01:28:53" (1/1) ... [2024-11-22 01:28:53,682 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6aafd67d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 01:28:53, skipping insertion in model container [2024-11-22 01:28:53,682 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 22.11 01:28:53" (1/1) ... [2024-11-22 01:28:53,700 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-22 01:28:53,884 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/hard-ll_unwindbound5.c[538,551] [2024-11-22 01:28:53,909 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-22 01:28:53,925 INFO L200 MainTranslator]: Completed pre-run [2024-11-22 01:28:53,937 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/hard-ll_unwindbound5.c[538,551] [2024-11-22 01:28:53,948 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-22 01:28:53,969 INFO L204 MainTranslator]: Completed translation [2024-11-22 01:28:53,970 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 01:28:53 WrapperNode [2024-11-22 01:28:53,970 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-22 01:28:53,971 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-22 01:28:53,971 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-22 01:28:53,971 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-22 01:28:53,978 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 01:28:53" (1/1) ... [2024-11-22 01:28:53,988 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 01:28:53" (1/1) ... [2024-11-22 01:28:54,015 INFO L138 Inliner]: procedures = 14, calls = 15, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 66 [2024-11-22 01:28:54,015 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-22 01:28:54,016 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-22 01:28:54,016 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-22 01:28:54,017 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-22 01:28:54,027 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 01:28:53" (1/1) ... [2024-11-22 01:28:54,028 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 01:28:53" (1/1) ... [2024-11-22 01:28:54,030 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 01:28:53" (1/1) ... [2024-11-22 01:28:54,046 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-11-22 01:28:54,046 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 01:28:53" (1/1) ... [2024-11-22 01:28:54,046 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 01:28:53" (1/1) ... [2024-11-22 01:28:54,050 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 01:28:53" (1/1) ... [2024-11-22 01:28:54,053 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 01:28:53" (1/1) ... [2024-11-22 01:28:54,054 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 01:28:53" (1/1) ... [2024-11-22 01:28:54,055 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 01:28:53" (1/1) ... [2024-11-22 01:28:54,057 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-22 01:28:54,058 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-22 01:28:54,058 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-22 01:28:54,058 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-22 01:28:54,059 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 01:28:53" (1/1) ... [2024-11-22 01:28:54,065 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-22 01:28:54,079 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:28:54,098 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-22 01:28:54,101 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-22 01:28:54,152 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-22 01:28:54,153 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-22 01:28:54,153 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-22 01:28:54,153 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-22 01:28:54,153 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-22 01:28:54,153 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-22 01:28:54,222 INFO L238 CfgBuilder]: Building ICFG [2024-11-22 01:28:54,224 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-22 01:28:54,450 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2024-11-22 01:28:54,450 INFO L287 CfgBuilder]: Performing block encoding [2024-11-22 01:28:54,466 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-22 01:28:54,466 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-22 01:28:54,467 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.11 01:28:54 BoogieIcfgContainer [2024-11-22 01:28:54,467 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-22 01:28:54,470 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-22 01:28:54,471 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-22 01:28:54,474 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-22 01:28:54,474 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 22.11 01:28:53" (1/3) ... [2024-11-22 01:28:54,475 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4b23dd55 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.11 01:28:54, skipping insertion in model container [2024-11-22 01:28:54,475 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.11 01:28:53" (2/3) ... [2024-11-22 01:28:54,476 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4b23dd55 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.11 01:28:54, skipping insertion in model container [2024-11-22 01:28:54,476 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.11 01:28:54" (3/3) ... [2024-11-22 01:28:54,479 INFO L112 eAbstractionObserver]: Analyzing ICFG hard-ll_unwindbound5.c [2024-11-22 01:28:54,496 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-22 01:28:54,497 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-22 01:28:54,562 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-22 01:28:54,571 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;@71ed8e06, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-22 01:28:54,572 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-22 01:28:54,577 INFO L276 IsEmpty]: Start isEmpty. Operand has 28 states, 18 states have (on average 1.5555555555555556) internal successors, (28), 19 states have internal predecessors, (28), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-22 01:28:54,585 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2024-11-22 01:28:54,585 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:28:54,586 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:28:54,587 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:28:54,591 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:28:54,592 INFO L85 PathProgramCache]: Analyzing trace with hash -712527539, now seen corresponding path program 1 times [2024-11-22 01:28:54,598 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:28:54,598 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [545294600] [2024-11-22 01:28:54,599 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:28:54,599 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:28:54,682 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:28:54,727 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-22 01:28:54,728 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:28:54,728 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [545294600] [2024-11-22 01:28:54,729 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [545294600] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-22 01:28:54,729 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-22 01:28:54,729 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-22 01:28:54,730 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [756224447] [2024-11-22 01:28:54,731 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-22 01:28:54,737 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-22 01:28:54,738 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:28:54,761 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-22 01:28:54,761 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-22 01:28:54,763 INFO L87 Difference]: Start difference. First operand has 28 states, 18 states have (on average 1.5555555555555556) internal successors, (28), 19 states have internal predecessors, (28), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-22 01:28:54,779 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:28:54,780 INFO L93 Difference]: Finished difference Result 53 states and 87 transitions. [2024-11-22 01:28:54,780 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-22 01:28:54,781 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 10 [2024-11-22 01:28:54,781 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:28:54,788 INFO L225 Difference]: With dead ends: 53 [2024-11-22 01:28:54,788 INFO L226 Difference]: Without dead ends: 24 [2024-11-22 01:28:54,791 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-22 01:28:54,794 INFO L432 NwaCegarLoop]: 38 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, 38 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-22 01:28:54,796 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-22 01:28:54,811 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2024-11-22 01:28:54,832 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2024-11-22 01:28:54,835 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 15 states have (on average 1.4) internal successors, (21), 16 states have internal predecessors, (21), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-22 01:28:54,837 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 34 transitions. [2024-11-22 01:28:54,840 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 34 transitions. Word has length 10 [2024-11-22 01:28:54,840 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:28:54,840 INFO L471 AbstractCegarLoop]: Abstraction has 24 states and 34 transitions. [2024-11-22 01:28:54,841 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-22 01:28:54,841 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 34 transitions. [2024-11-22 01:28:54,842 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2024-11-22 01:28:54,842 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:28:54,842 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:28:54,842 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-22 01:28:54,843 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:28:54,843 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:28:54,844 INFO L85 PathProgramCache]: Analyzing trace with hash -1983932575, now seen corresponding path program 1 times [2024-11-22 01:28:54,844 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:28:54,844 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1953530852] [2024-11-22 01:28:54,844 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:28:54,845 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:28:54,882 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:28:55,049 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-22 01:28:55,049 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:28:55,050 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1953530852] [2024-11-22 01:28:55,050 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1953530852] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-22 01:28:55,050 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-22 01:28:55,050 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-22 01:28:55,051 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [254477793] [2024-11-22 01:28:55,051 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-22 01:28:55,052 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-22 01:28:55,052 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:28:55,053 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-22 01:28:55,053 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-22 01:28:55,053 INFO L87 Difference]: Start difference. First operand 24 states and 34 transitions. Second operand has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-22 01:28:55,139 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:28:55,139 INFO L93 Difference]: Finished difference Result 38 states and 53 transitions. [2024-11-22 01:28:55,140 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-22 01:28:55,140 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 10 [2024-11-22 01:28:55,141 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:28:55,142 INFO L225 Difference]: With dead ends: 38 [2024-11-22 01:28:55,142 INFO L226 Difference]: Without dead ends: 36 [2024-11-22 01:28:55,142 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-22 01:28:55,143 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 12 mSDsluCounter, 74 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 104 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 22 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-22 01:28:55,144 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 104 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-22 01:28:55,145 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2024-11-22 01:28:55,164 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 28. [2024-11-22 01:28:55,164 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-22 01:28:55,165 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 37 transitions. [2024-11-22 01:28:55,166 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 37 transitions. Word has length 10 [2024-11-22 01:28:55,166 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:28:55,166 INFO L471 AbstractCegarLoop]: Abstraction has 28 states and 37 transitions. [2024-11-22 01:28:55,166 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-22 01:28:55,167 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 37 transitions. [2024-11-22 01:28:55,167 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2024-11-22 01:28:55,167 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:28:55,168 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:28:55,168 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-22 01:28:55,168 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:28:55,169 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:28:55,169 INFO L85 PathProgramCache]: Analyzing trace with hash 1787143384, now seen corresponding path program 1 times [2024-11-22 01:28:55,169 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:28:55,169 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [345079835] [2024-11-22 01:28:55,170 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:28:55,170 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:28:55,190 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:28:55,266 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-22 01:28:55,267 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:28:55,267 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [345079835] [2024-11-22 01:28:55,267 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [345079835] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-22 01:28:55,267 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-22 01:28:55,268 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-22 01:28:55,268 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [949555472] [2024-11-22 01:28:55,268 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-22 01:28:55,268 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-22 01:28:55,268 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:28:55,269 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-22 01:28:55,271 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-22 01:28:55,272 INFO L87 Difference]: Start difference. First operand 28 states and 37 transitions. Second operand has 4 states, 4 states have (on average 2.75) internal successors, (11), 3 states have internal predecessors, (11), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-22 01:28:55,296 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:28:55,296 INFO L93 Difference]: Finished difference Result 44 states and 59 transitions. [2024-11-22 01:28:55,296 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-22 01:28:55,297 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 3 states have internal predecessors, (11), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 12 [2024-11-22 01:28:55,297 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:28:55,298 INFO L225 Difference]: With dead ends: 44 [2024-11-22 01:28:55,298 INFO L226 Difference]: Without dead ends: 30 [2024-11-22 01:28:55,298 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-22 01:28:55,300 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 0 mSDsluCounter, 57 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 89 SdHoareTripleChecker+Invalid, 9 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-22 01:28:55,302 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 89 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-22 01:28:55,304 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2024-11-22 01:28:55,312 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 30. [2024-11-22 01:28:55,313 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 20 states have (on average 1.3) internal successors, (26), 21 states have internal predecessors, (26), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-22 01:28:55,314 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 39 transitions. [2024-11-22 01:28:55,314 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 39 transitions. Word has length 12 [2024-11-22 01:28:55,314 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:28:55,314 INFO L471 AbstractCegarLoop]: Abstraction has 30 states and 39 transitions. [2024-11-22 01:28:55,315 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 3 states have internal predecessors, (11), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-22 01:28:55,315 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 39 transitions. [2024-11-22 01:28:55,315 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2024-11-22 01:28:55,315 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:28:55,316 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:28:55,316 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-11-22 01:28:55,316 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:28:55,317 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:28:55,317 INFO L85 PathProgramCache]: Analyzing trace with hash 472519838, now seen corresponding path program 1 times [2024-11-22 01:28:55,317 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:28:55,318 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1455068192] [2024-11-22 01:28:55,318 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:28:55,321 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:28:55,345 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:28:55,488 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-22 01:28:55,489 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:28:55,489 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1455068192] [2024-11-22 01:28:55,489 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1455068192] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-22 01:28:55,489 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-22 01:28:55,489 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-22 01:28:55,489 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [979046325] [2024-11-22 01:28:55,490 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-22 01:28:55,490 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-22 01:28:55,490 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:28:55,493 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-22 01:28:55,494 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-22 01:28:55,494 INFO L87 Difference]: Start difference. First operand 30 states and 39 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-22 01:28:55,587 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:28:55,591 INFO L93 Difference]: Finished difference Result 44 states and 58 transitions. [2024-11-22 01:28:55,592 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-22 01:28:55,592 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 15 [2024-11-22 01:28:55,592 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:28:55,593 INFO L225 Difference]: With dead ends: 44 [2024-11-22 01:28:55,593 INFO L226 Difference]: Without dead ends: 42 [2024-11-22 01:28:55,594 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-22 01:28:55,595 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 12 mSDsluCounter, 71 mSDsCounter, 0 mSdLazyCounter, 33 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 101 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 33 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-22 01:28:55,595 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 101 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 33 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-22 01:28:55,596 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2024-11-22 01:28:55,609 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 34. [2024-11-22 01:28:55,610 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 23 states have (on average 1.2608695652173914) internal successors, (29), 24 states have internal predecessors, (29), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-22 01:28:55,611 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 42 transitions. [2024-11-22 01:28:55,611 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 42 transitions. Word has length 15 [2024-11-22 01:28:55,611 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:28:55,611 INFO L471 AbstractCegarLoop]: Abstraction has 34 states and 42 transitions. [2024-11-22 01:28:55,612 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-22 01:28:55,612 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 42 transitions. [2024-11-22 01:28:55,612 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2024-11-22 01:28:55,613 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:28:55,613 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:28:55,613 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2024-11-22 01:28:55,613 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:28:55,614 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:28:55,614 INFO L85 PathProgramCache]: Analyzing trace with hash 838495553, now seen corresponding path program 1 times [2024-11-22 01:28:55,614 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:28:55,614 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [543930446] [2024-11-22 01:28:55,615 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:28:55,615 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:28:55,629 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-22 01:28:55,631 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1770900098] [2024-11-22 01:28:55,632 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:28:55,632 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:28:55,632 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:28:55,635 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-22 01:28:55,636 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-22 01:28:55,685 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:28:55,687 INFO L255 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-22 01:28:55,693 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:28:55,800 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-22 01:28:55,800 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-22 01:28:55,801 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:28:55,801 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [543930446] [2024-11-22 01:28:55,801 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-22 01:28:55,802 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1770900098] [2024-11-22 01:28:55,802 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1770900098] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-22 01:28:55,802 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-22 01:28:55,803 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-22 01:28:55,805 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1752867251] [2024-11-22 01:28:55,805 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-22 01:28:55,806 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-22 01:28:55,806 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:28:55,806 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-22 01:28:55,806 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-22 01:28:55,807 INFO L87 Difference]: Start difference. First operand 34 states and 42 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-22 01:28:55,896 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:28:55,897 INFO L93 Difference]: Finished difference Result 63 states and 85 transitions. [2024-11-22 01:28:55,898 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-22 01:28:55,898 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 20 [2024-11-22 01:28:55,900 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:28:55,902 INFO L225 Difference]: With dead ends: 63 [2024-11-22 01:28:55,902 INFO L226 Difference]: Without dead ends: 48 [2024-11-22 01:28:55,902 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 20 GetRequests, 16 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-22 01:28:55,907 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 7 mSDsluCounter, 75 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 105 SdHoareTripleChecker+Invalid, 41 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-22 01:28:55,908 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 105 Invalid, 41 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-22 01:28:55,909 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2024-11-22 01:28:55,924 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 48. [2024-11-22 01:28:55,927 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 30 states have (on average 1.2666666666666666) internal successors, (38), 32 states have internal predecessors, (38), 13 states have call successors, (13), 4 states have call predecessors, (13), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-22 01:28:55,928 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 62 transitions. [2024-11-22 01:28:55,932 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 62 transitions. Word has length 20 [2024-11-22 01:28:55,932 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:28:55,933 INFO L471 AbstractCegarLoop]: Abstraction has 48 states and 62 transitions. [2024-11-22 01:28:55,933 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-22 01:28:55,933 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 62 transitions. [2024-11-22 01:28:55,935 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2024-11-22 01:28:55,935 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:28:55,935 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:28:55,944 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-22 01:28:56,136 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:28:56,136 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:28:56,138 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:28:56,138 INFO L85 PathProgramCache]: Analyzing trace with hash 414140572, now seen corresponding path program 1 times [2024-11-22 01:28:56,139 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:28:56,140 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [805998732] [2024-11-22 01:28:56,140 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:28:56,140 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:28:56,154 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:28:56,218 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-22 01:28:56,218 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:28:56,219 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [805998732] [2024-11-22 01:28:56,219 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [805998732] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-22 01:28:56,219 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-22 01:28:56,219 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-22 01:28:56,219 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1624693010] [2024-11-22 01:28:56,219 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-22 01:28:56,220 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-22 01:28:56,220 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:28:56,220 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-22 01:28:56,220 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-11-22 01:28:56,221 INFO L87 Difference]: Start difference. First operand 48 states and 62 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-22 01:28:56,265 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:28:56,265 INFO L93 Difference]: Finished difference Result 67 states and 77 transitions. [2024-11-22 01:28:56,266 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-22 01:28:56,266 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 28 [2024-11-22 01:28:56,266 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:28:56,268 INFO L225 Difference]: With dead ends: 67 [2024-11-22 01:28:56,270 INFO L226 Difference]: Without dead ends: 60 [2024-11-22 01:28:56,270 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-11-22 01:28:56,271 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 7 mSDsluCounter, 77 mSDsCounter, 0 mSdLazyCounter, 20 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 108 SdHoareTripleChecker+Invalid, 20 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 20 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-22 01:28:56,272 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 108 Invalid, 20 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 20 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-22 01:28:56,272 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2024-11-22 01:28:56,286 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 59. [2024-11-22 01:28:56,289 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 39 states have (on average 1.1794871794871795) internal successors, (46), 40 states have internal predecessors, (46), 12 states have call successors, (12), 7 states have call predecessors, (12), 7 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-22 01:28:56,290 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 69 transitions. [2024-11-22 01:28:56,293 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 69 transitions. Word has length 28 [2024-11-22 01:28:56,293 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:28:56,293 INFO L471 AbstractCegarLoop]: Abstraction has 59 states and 69 transitions. [2024-11-22 01:28:56,293 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-22 01:28:56,294 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 69 transitions. [2024-11-22 01:28:56,294 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2024-11-22 01:28:56,294 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:28:56,294 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:28:56,295 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2024-11-22 01:28:56,295 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:28:56,295 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:28:56,295 INFO L85 PathProgramCache]: Analyzing trace with hash 415868450, now seen corresponding path program 1 times [2024-11-22 01:28:56,295 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:28:56,295 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1890033943] [2024-11-22 01:28:56,296 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:28:56,296 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:28:56,312 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-22 01:28:56,313 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [654364084] [2024-11-22 01:28:56,313 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:28:56,313 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:28:56,313 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:28:56,316 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-22 01:28:56,319 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-22 01:28:56,367 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:28:56,368 INFO L255 TraceCheckSpWp]: Trace formula consists of 83 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-22 01:28:56,370 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:28:56,470 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-22 01:28:56,471 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-22 01:28:56,471 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:28:56,471 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1890033943] [2024-11-22 01:28:56,471 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-22 01:28:56,471 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [654364084] [2024-11-22 01:28:56,471 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [654364084] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-22 01:28:56,472 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-22 01:28:56,472 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-22 01:28:56,472 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [160904186] [2024-11-22 01:28:56,472 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-22 01:28:56,473 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-22 01:28:56,473 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:28:56,473 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-22 01:28:56,474 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-22 01:28:56,474 INFO L87 Difference]: Start difference. First operand 59 states and 69 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-22 01:28:56,543 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:28:56,543 INFO L93 Difference]: Finished difference Result 73 states and 88 transitions. [2024-11-22 01:28:56,544 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-22 01:28:56,544 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 28 [2024-11-22 01:28:56,544 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:28:56,545 INFO L225 Difference]: With dead ends: 73 [2024-11-22 01:28:56,546 INFO L226 Difference]: Without dead ends: 71 [2024-11-22 01:28:56,547 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 28 GetRequests, 24 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-22 01:28:56,547 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 9 mSDsluCounter, 61 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 85 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-22 01:28:56,548 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 85 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-22 01:28:56,549 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2024-11-22 01:28:56,565 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 70. [2024-11-22 01:28:56,568 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 70 states, 46 states have (on average 1.2173913043478262) internal successors, (56), 48 states have internal predecessors, (56), 15 states have call successors, (15), 8 states have call predecessors, (15), 8 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2024-11-22 01:28:56,570 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 70 states to 70 states and 85 transitions. [2024-11-22 01:28:56,571 INFO L78 Accepts]: Start accepts. Automaton has 70 states and 85 transitions. Word has length 28 [2024-11-22 01:28:56,571 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:28:56,571 INFO L471 AbstractCegarLoop]: Abstraction has 70 states and 85 transitions. [2024-11-22 01:28:56,571 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-22 01:28:56,571 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 85 transitions. [2024-11-22 01:28:56,572 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2024-11-22 01:28:56,572 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:28:56,573 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:28:56,581 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-22 01:28:56,774 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,SelfDestructingSolverStorable6 [2024-11-22 01:28:56,774 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:28:56,775 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:28:56,775 INFO L85 PathProgramCache]: Analyzing trace with hash -1091220578, now seen corresponding path program 1 times [2024-11-22 01:28:56,775 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:28:56,775 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [969289667] [2024-11-22 01:28:56,775 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:28:56,775 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:28:56,787 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:28:56,854 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-22 01:28:56,855 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:28:56,855 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [969289667] [2024-11-22 01:28:56,855 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [969289667] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-22 01:28:56,855 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1432027788] [2024-11-22 01:28:56,856 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:28:56,856 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:28:56,856 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:28:56,858 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-22 01:28:56,860 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-22 01:28:56,901 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:28:56,903 INFO L255 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-22 01:28:56,905 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:28:56,963 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 18 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2024-11-22 01:28:56,963 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-22 01:28:57,039 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-22 01:28:57,039 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1432027788] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-22 01:28:57,040 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-22 01:28:57,042 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 4, 5] total 8 [2024-11-22 01:28:57,042 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [231287780] [2024-11-22 01:28:57,042 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-22 01:28:57,043 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-22 01:28:57,043 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:28:57,043 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-22 01:28:57,043 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2024-11-22 01:28:57,044 INFO L87 Difference]: Start difference. First operand 70 states and 85 transitions. Second operand has 8 states, 8 states have (on average 3.875) internal successors, (31), 8 states have internal predecessors, (31), 3 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2024-11-22 01:28:57,204 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:28:57,204 INFO L93 Difference]: Finished difference Result 157 states and 192 transitions. [2024-11-22 01:28:57,205 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-22 01:28:57,205 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.875) internal successors, (31), 8 states have internal predecessors, (31), 3 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) Word has length 35 [2024-11-22 01:28:57,205 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:28:57,208 INFO L225 Difference]: With dead ends: 157 [2024-11-22 01:28:57,208 INFO L226 Difference]: Without dead ends: 132 [2024-11-22 01:28:57,208 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 67 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=40, Invalid=70, Unknown=0, NotChecked=0, Total=110 [2024-11-22 01:28:57,209 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 46 mSDsluCounter, 131 mSDsCounter, 0 mSdLazyCounter, 68 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 46 SdHoareTripleChecker+Valid, 164 SdHoareTripleChecker+Invalid, 71 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 68 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-22 01:28:57,209 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [46 Valid, 164 Invalid, 71 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 68 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-22 01:28:57,210 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 132 states. [2024-11-22 01:28:57,225 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 132 to 125. [2024-11-22 01:28:57,226 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 125 states, 81 states have (on average 1.1975308641975309) internal successors, (97), 85 states have internal predecessors, (97), 27 states have call successors, (27), 16 states have call predecessors, (27), 16 states have return successors, (24), 23 states have call predecessors, (24), 24 states have call successors, (24) [2024-11-22 01:28:57,227 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 125 states to 125 states and 148 transitions. [2024-11-22 01:28:57,228 INFO L78 Accepts]: Start accepts. Automaton has 125 states and 148 transitions. Word has length 35 [2024-11-22 01:28:57,228 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:28:57,228 INFO L471 AbstractCegarLoop]: Abstraction has 125 states and 148 transitions. [2024-11-22 01:28:57,228 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.875) internal successors, (31), 8 states have internal predecessors, (31), 3 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2024-11-22 01:28:57,228 INFO L276 IsEmpty]: Start isEmpty. Operand 125 states and 148 transitions. [2024-11-22 01:28:57,229 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2024-11-22 01:28:57,229 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:28:57,229 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:28:57,238 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-22 01:28:57,430 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:28:57,430 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:28:57,431 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:28:57,431 INFO L85 PathProgramCache]: Analyzing trace with hash 1884102282, now seen corresponding path program 1 times [2024-11-22 01:28:57,431 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:28:57,431 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [60865573] [2024-11-22 01:28:57,431 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:28:57,431 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:28:57,446 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-22 01:28:57,447 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2946066] [2024-11-22 01:28:57,447 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:28:57,448 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:28:57,448 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:28:57,450 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-22 01:28:57,455 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-22 01:28:57,497 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:28:57,498 INFO L255 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-22 01:28:57,500 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:28:57,629 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 5 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-22 01:28:57,629 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-22 01:28:57,725 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-22 01:28:57,725 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:28:57,725 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [60865573] [2024-11-22 01:28:57,725 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-22 01:28:57,725 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2946066] [2024-11-22 01:28:57,725 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2946066] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-22 01:28:57,725 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-22 01:28:57,726 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2024-11-22 01:28:57,726 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1428822805] [2024-11-22 01:28:57,726 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-22 01:28:57,726 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-22 01:28:57,726 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:28:57,727 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-22 01:28:57,727 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-22 01:28:57,727 INFO L87 Difference]: Start difference. First operand 125 states and 148 transitions. Second operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-22 01:28:57,813 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:28:57,813 INFO L93 Difference]: Finished difference Result 148 states and 176 transitions. [2024-11-22 01:28:57,813 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-22 01:28:57,814 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 38 [2024-11-22 01:28:57,814 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:28:57,815 INFO L225 Difference]: With dead ends: 148 [2024-11-22 01:28:57,815 INFO L226 Difference]: Without dead ends: 142 [2024-11-22 01:28:57,816 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 75 GetRequests, 67 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-22 01:28:57,816 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 8 mSDsluCounter, 69 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 99 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-22 01:28:57,817 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 99 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-22 01:28:57,817 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 142 states. [2024-11-22 01:28:57,836 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 142 to 134. [2024-11-22 01:28:57,836 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 134 states, 88 states have (on average 1.1704545454545454) internal successors, (103), 92 states have internal predecessors, (103), 28 states have call successors, (28), 18 states have call predecessors, (28), 17 states have return successors, (26), 23 states have call predecessors, (26), 26 states have call successors, (26) [2024-11-22 01:28:57,837 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 134 states to 134 states and 157 transitions. [2024-11-22 01:28:57,838 INFO L78 Accepts]: Start accepts. Automaton has 134 states and 157 transitions. Word has length 38 [2024-11-22 01:28:57,838 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:28:57,838 INFO L471 AbstractCegarLoop]: Abstraction has 134 states and 157 transitions. [2024-11-22 01:28:57,838 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-22 01:28:57,838 INFO L276 IsEmpty]: Start isEmpty. Operand 134 states and 157 transitions. [2024-11-22 01:28:57,839 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2024-11-22 01:28:57,839 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:28:57,839 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:28:57,849 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-11-22 01:28:58,043 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:28:58,044 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:28:58,044 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:28:58,045 INFO L85 PathProgramCache]: Analyzing trace with hash -1909657797, now seen corresponding path program 1 times [2024-11-22 01:28:58,045 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:28:58,045 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [650088773] [2024-11-22 01:28:58,045 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:28:58,045 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:28:58,056 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:28:58,158 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-11-22 01:28:58,159 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:28:58,159 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [650088773] [2024-11-22 01:28:58,159 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [650088773] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-22 01:28:58,159 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-22 01:28:58,159 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-22 01:28:58,159 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2102579499] [2024-11-22 01:28:58,159 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-22 01:28:58,159 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-22 01:28:58,160 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:28:58,160 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-22 01:28:58,160 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-22 01:28:58,160 INFO L87 Difference]: Start difference. First operand 134 states and 157 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 1 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2024-11-22 01:28:58,209 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:28:58,209 INFO L93 Difference]: Finished difference Result 139 states and 161 transitions. [2024-11-22 01:28:58,210 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-22 01:28:58,210 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), 1 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) Word has length 44 [2024-11-22 01:28:58,211 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:28:58,212 INFO L225 Difference]: With dead ends: 139 [2024-11-22 01:28:58,212 INFO L226 Difference]: Without dead ends: 120 [2024-11-22 01:28:58,213 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-22 01:28:58,213 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 1 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 118 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-22 01:28:58,214 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 118 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-22 01:28:58,214 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 120 states. [2024-11-22 01:28:58,237 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 120 to 120. [2024-11-22 01:28:58,238 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 120 states, 79 states have (on average 1.1772151898734178) internal successors, (93), 82 states have internal predecessors, (93), 25 states have call successors, (25), 16 states have call predecessors, (25), 15 states have return successors, (23), 21 states have call predecessors, (23), 23 states have call successors, (23) [2024-11-22 01:28:58,239 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 120 states to 120 states and 141 transitions. [2024-11-22 01:28:58,240 INFO L78 Accepts]: Start accepts. Automaton has 120 states and 141 transitions. Word has length 44 [2024-11-22 01:28:58,240 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:28:58,240 INFO L471 AbstractCegarLoop]: Abstraction has 120 states and 141 transitions. [2024-11-22 01:28:58,241 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), 1 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2024-11-22 01:28:58,241 INFO L276 IsEmpty]: Start isEmpty. Operand 120 states and 141 transitions. [2024-11-22 01:28:58,242 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2024-11-22 01:28:58,242 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:28:58,242 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:28:58,242 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9 [2024-11-22 01:28:58,242 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:28:58,242 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:28:58,243 INFO L85 PathProgramCache]: Analyzing trace with hash -785132454, now seen corresponding path program 1 times [2024-11-22 01:28:58,243 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:28:58,243 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1652456896] [2024-11-22 01:28:58,243 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:28:58,243 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:28:58,259 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:28:58,339 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 14 proven. 6 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2024-11-22 01:28:58,340 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:28:58,340 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1652456896] [2024-11-22 01:28:58,340 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1652456896] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-22 01:28:58,342 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1076138780] [2024-11-22 01:28:58,342 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:28:58,343 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:28:58,343 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:28:58,346 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-22 01:28:58,347 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-22 01:28:58,396 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:28:58,397 INFO L255 TraceCheckSpWp]: Trace formula consists of 129 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-22 01:28:58,399 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:28:58,457 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 36 proven. 42 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2024-11-22 01:28:58,457 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-22 01:28:58,537 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 14 proven. 6 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2024-11-22 01:28:58,537 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1076138780] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-22 01:28:58,537 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-22 01:28:58,537 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5, 6] total 9 [2024-11-22 01:28:58,538 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1609461177] [2024-11-22 01:28:58,538 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-22 01:28:58,538 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-22 01:28:58,539 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:28:58,539 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-22 01:28:58,539 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=46, Unknown=0, NotChecked=0, Total=72 [2024-11-22 01:28:58,540 INFO L87 Difference]: Start difference. First operand 120 states and 141 transitions. Second operand has 9 states, 9 states have (on average 4.222222222222222) internal successors, (38), 9 states have internal predecessors, (38), 5 states have call successors, (21), 4 states have call predecessors, (21), 4 states have return successors, (20), 5 states have call predecessors, (20), 5 states have call successors, (20) [2024-11-22 01:28:58,656 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:28:58,656 INFO L93 Difference]: Finished difference Result 196 states and 234 transitions. [2024-11-22 01:28:58,656 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-22 01:28:58,657 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 4.222222222222222) internal successors, (38), 9 states have internal predecessors, (38), 5 states have call successors, (21), 4 states have call predecessors, (21), 4 states have return successors, (20), 5 states have call predecessors, (20), 5 states have call successors, (20) Word has length 51 [2024-11-22 01:28:58,657 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:28:58,658 INFO L225 Difference]: With dead ends: 196 [2024-11-22 01:28:58,658 INFO L226 Difference]: Without dead ends: 175 [2024-11-22 01:28:58,659 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 108 GetRequests, 98 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=37, Invalid=73, Unknown=0, NotChecked=0, Total=110 [2024-11-22 01:28:58,660 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 43 mSDsluCounter, 106 mSDsCounter, 0 mSdLazyCounter, 58 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 43 SdHoareTripleChecker+Valid, 141 SdHoareTripleChecker+Invalid, 60 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 58 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-22 01:28:58,660 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [43 Valid, 141 Invalid, 60 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 58 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-22 01:28:58,660 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 175 states. [2024-11-22 01:28:58,683 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 175 to 170. [2024-11-22 01:28:58,683 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 170 states, 112 states have (on average 1.1785714285714286) internal successors, (132), 118 states have internal predecessors, (132), 37 states have call successors, (37), 21 states have call predecessors, (37), 20 states have return successors, (34), 30 states have call predecessors, (34), 34 states have call successors, (34) [2024-11-22 01:28:58,685 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 170 states to 170 states and 203 transitions. [2024-11-22 01:28:58,685 INFO L78 Accepts]: Start accepts. Automaton has 170 states and 203 transitions. Word has length 51 [2024-11-22 01:28:58,685 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:28:58,685 INFO L471 AbstractCegarLoop]: Abstraction has 170 states and 203 transitions. [2024-11-22 01:28:58,686 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 4.222222222222222) internal successors, (38), 9 states have internal predecessors, (38), 5 states have call successors, (21), 4 states have call predecessors, (21), 4 states have return successors, (20), 5 states have call predecessors, (20), 5 states have call successors, (20) [2024-11-22 01:28:58,686 INFO L276 IsEmpty]: Start isEmpty. Operand 170 states and 203 transitions. [2024-11-22 01:28:58,687 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2024-11-22 01:28:58,687 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:28:58,687 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:28:58,696 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-22 01:28:58,891 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2024-11-22 01:28:58,892 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:28:58,892 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:28:58,892 INFO L85 PathProgramCache]: Analyzing trace with hash 98519191, now seen corresponding path program 1 times [2024-11-22 01:28:58,892 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:28:58,892 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [827982487] [2024-11-22 01:28:58,892 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:28:58,893 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:28:58,927 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-22 01:28:58,928 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1225319415] [2024-11-22 01:28:58,928 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:28:58,928 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:28:58,929 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:28:58,931 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-22 01:28:58,933 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-22 01:28:58,986 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:28:58,990 INFO L255 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 33 conjuncts are in the unsatisfiable core [2024-11-22 01:28:58,993 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:28:59,612 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 16 proven. 9 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2024-11-22 01:28:59,612 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-22 01:29:01,802 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 16 proven. 9 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2024-11-22 01:29:01,803 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:29:01,803 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [827982487] [2024-11-22 01:29:01,803 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-22 01:29:01,803 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1225319415] [2024-11-22 01:29:01,803 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1225319415] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-22 01:29:01,803 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-22 01:29:01,803 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9] total 18 [2024-11-22 01:29:01,804 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [952900693] [2024-11-22 01:29:01,804 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-22 01:29:01,805 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2024-11-22 01:29:01,805 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:29:01,805 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2024-11-22 01:29:01,807 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=62, Invalid=244, Unknown=0, NotChecked=0, Total=306 [2024-11-22 01:29:01,807 INFO L87 Difference]: Start difference. First operand 170 states and 203 transitions. Second operand has 18 states, 18 states have (on average 2.1666666666666665) internal successors, (39), 16 states have internal predecessors, (39), 8 states have call successors, (18), 3 states have call predecessors, (18), 1 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2024-11-22 01:29:03,018 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:29:03,018 INFO L93 Difference]: Finished difference Result 283 states and 361 transitions. [2024-11-22 01:29:03,020 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-11-22 01:29:03,020 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 2.1666666666666665) internal successors, (39), 16 states have internal predecessors, (39), 8 states have call successors, (18), 3 states have call predecessors, (18), 1 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) Word has length 60 [2024-11-22 01:29:03,020 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:29:03,023 INFO L225 Difference]: With dead ends: 283 [2024-11-22 01:29:03,023 INFO L226 Difference]: Without dead ends: 230 [2024-11-22 01:29:03,025 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 127 GetRequests, 102 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 139 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=152, Invalid=550, Unknown=0, NotChecked=0, Total=702 [2024-11-22 01:29:03,027 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 94 mSDsluCounter, 287 mSDsCounter, 0 mSdLazyCounter, 262 mSolverCounterSat, 94 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 97 SdHoareTripleChecker+Valid, 322 SdHoareTripleChecker+Invalid, 356 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 94 IncrementalHoareTripleChecker+Valid, 262 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2024-11-22 01:29:03,027 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [97 Valid, 322 Invalid, 356 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [94 Valid, 262 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2024-11-22 01:29:03,028 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 230 states. [2024-11-22 01:29:03,072 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 230 to 198. [2024-11-22 01:29:03,073 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 198 states, 134 states have (on average 1.1865671641791045) internal successors, (159), 140 states have internal predecessors, (159), 39 states have call successors, (39), 24 states have call predecessors, (39), 24 states have return successors, (37), 33 states have call predecessors, (37), 37 states have call successors, (37) [2024-11-22 01:29:03,075 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 198 states to 198 states and 235 transitions. [2024-11-22 01:29:03,076 INFO L78 Accepts]: Start accepts. Automaton has 198 states and 235 transitions. Word has length 60 [2024-11-22 01:29:03,076 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:29:03,076 INFO L471 AbstractCegarLoop]: Abstraction has 198 states and 235 transitions. [2024-11-22 01:29:03,076 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 2.1666666666666665) internal successors, (39), 16 states have internal predecessors, (39), 8 states have call successors, (18), 3 states have call predecessors, (18), 1 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2024-11-22 01:29:03,076 INFO L276 IsEmpty]: Start isEmpty. Operand 198 states and 235 transitions. [2024-11-22 01:29:03,077 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 72 [2024-11-22 01:29:03,078 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:29:03,079 INFO L215 NwaCegarLoop]: trace histogram [11, 10, 10, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:29:03,087 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-22 01:29:03,282 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:29:03,283 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:29:03,284 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:29:03,284 INFO L85 PathProgramCache]: Analyzing trace with hash -902942769, now seen corresponding path program 1 times [2024-11-22 01:29:03,284 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:29:03,284 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1167848083] [2024-11-22 01:29:03,284 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:29:03,284 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:29:03,315 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-22 01:29:03,317 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [792916080] [2024-11-22 01:29:03,317 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:29:03,317 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:29:03,317 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:29:03,319 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-22 01:29:03,321 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-22 01:29:03,373 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:29:03,375 INFO L255 TraceCheckSpWp]: Trace formula consists of 173 conjuncts, 29 conjuncts are in the unsatisfiable core [2024-11-22 01:29:03,377 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:29:03,888 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 20 proven. 11 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2024-11-22 01:29:03,888 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-22 01:29:04,655 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 20 proven. 11 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2024-11-22 01:29:04,655 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:29:04,655 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1167848083] [2024-11-22 01:29:04,655 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-22 01:29:04,655 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [792916080] [2024-11-22 01:29:04,656 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [792916080] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-22 01:29:04,656 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-22 01:29:04,656 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 9] total 19 [2024-11-22 01:29:04,656 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [992654077] [2024-11-22 01:29:04,656 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-22 01:29:04,656 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-22 01:29:04,656 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:29:04,657 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-22 01:29:04,657 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=275, Unknown=0, NotChecked=0, Total=342 [2024-11-22 01:29:04,658 INFO L87 Difference]: Start difference. First operand 198 states and 235 transitions. Second operand has 19 states, 18 states have (on average 2.2777777777777777) internal successors, (41), 17 states have internal predecessors, (41), 10 states have call successors, (22), 3 states have call predecessors, (22), 1 states have return successors, (20), 8 states have call predecessors, (20), 8 states have call successors, (20) [2024-11-22 01:29:05,392 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:29:05,392 INFO L93 Difference]: Finished difference Result 288 states and 362 transitions. [2024-11-22 01:29:05,392 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-11-22 01:29:05,393 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 18 states have (on average 2.2777777777777777) internal successors, (41), 17 states have internal predecessors, (41), 10 states have call successors, (22), 3 states have call predecessors, (22), 1 states have return successors, (20), 8 states have call predecessors, (20), 8 states have call successors, (20) Word has length 71 [2024-11-22 01:29:05,393 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:29:05,394 INFO L225 Difference]: With dead ends: 288 [2024-11-22 01:29:05,394 INFO L226 Difference]: Without dead ends: 247 [2024-11-22 01:29:05,395 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 151 GetRequests, 123 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 123 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=174, Invalid=696, Unknown=0, NotChecked=0, Total=870 [2024-11-22 01:29:05,396 INFO L432 NwaCegarLoop]: 50 mSDtfsCounter, 63 mSDsluCounter, 438 mSDsCounter, 0 mSdLazyCounter, 315 mSolverCounterSat, 54 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 66 SdHoareTripleChecker+Valid, 488 SdHoareTripleChecker+Invalid, 369 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 54 IncrementalHoareTripleChecker+Valid, 315 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-22 01:29:05,396 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [66 Valid, 488 Invalid, 369 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [54 Valid, 315 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-22 01:29:05,396 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 247 states. [2024-11-22 01:29:05,461 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 247 to 209. [2024-11-22 01:29:05,461 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 209 states, 142 states have (on average 1.1971830985915493) internal successors, (170), 145 states have internal predecessors, (170), 42 states have call successors, (42), 25 states have call predecessors, (42), 24 states have return successors, (40), 38 states have call predecessors, (40), 40 states have call successors, (40) [2024-11-22 01:29:05,463 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 209 states to 209 states and 252 transitions. [2024-11-22 01:29:05,464 INFO L78 Accepts]: Start accepts. Automaton has 209 states and 252 transitions. Word has length 71 [2024-11-22 01:29:05,465 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:29:05,465 INFO L471 AbstractCegarLoop]: Abstraction has 209 states and 252 transitions. [2024-11-22 01:29:05,465 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 18 states have (on average 2.2777777777777777) internal successors, (41), 17 states have internal predecessors, (41), 10 states have call successors, (22), 3 states have call predecessors, (22), 1 states have return successors, (20), 8 states have call predecessors, (20), 8 states have call successors, (20) [2024-11-22 01:29:05,466 INFO L276 IsEmpty]: Start isEmpty. Operand 209 states and 252 transitions. [2024-11-22 01:29:05,466 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2024-11-22 01:29:05,467 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:29:05,467 INFO L215 NwaCegarLoop]: trace histogram [11, 10, 10, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:29:05,476 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-22 01:29:05,670 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:29:05,671 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:29:05,671 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:29:05,671 INFO L85 PathProgramCache]: Analyzing trace with hash -1932765757, now seen corresponding path program 2 times [2024-11-22 01:29:05,671 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:29:05,671 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1515150027] [2024-11-22 01:29:05,671 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-22 01:29:05,671 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:29:05,694 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-22 01:29:05,694 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-22 01:29:05,902 INFO L134 CoverageAnalysis]: Checked inductivity of 218 backedges. 27 proven. 11 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2024-11-22 01:29:05,902 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:29:05,902 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1515150027] [2024-11-22 01:29:05,902 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1515150027] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-22 01:29:05,902 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1246451084] [2024-11-22 01:29:05,902 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-22 01:29:05,902 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:29:05,903 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:29:05,905 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-22 01:29:05,906 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-22 01:29:05,964 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-22 01:29:05,965 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-22 01:29:05,966 INFO L255 TraceCheckSpWp]: Trace formula consists of 186 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-22 01:29:05,970 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:29:06,008 INFO L134 CoverageAnalysis]: Checked inductivity of 218 backedges. 27 proven. 11 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2024-11-22 01:29:06,009 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-22 01:29:06,106 INFO L134 CoverageAnalysis]: Checked inductivity of 218 backedges. 27 proven. 11 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2024-11-22 01:29:06,107 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1246451084] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-22 01:29:06,107 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-22 01:29:06,107 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4, 4] total 5 [2024-11-22 01:29:06,107 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1300191357] [2024-11-22 01:29:06,107 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-22 01:29:06,108 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-22 01:29:06,108 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:29:06,108 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-22 01:29:06,109 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-11-22 01:29:06,109 INFO L87 Difference]: Start difference. First operand 209 states and 252 transitions. Second operand has 5 states, 5 states have (on average 6.6) internal successors, (33), 5 states have internal predecessors, (33), 4 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-22 01:29:06,202 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:29:06,203 INFO L93 Difference]: Finished difference Result 233 states and 285 transitions. [2024-11-22 01:29:06,203 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-22 01:29:06,203 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), 4 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 74 [2024-11-22 01:29:06,204 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:29:06,205 INFO L225 Difference]: With dead ends: 233 [2024-11-22 01:29:06,205 INFO L226 Difference]: Without dead ends: 204 [2024-11-22 01:29:06,206 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 151 GetRequests, 148 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-11-22 01:29:06,206 INFO L432 NwaCegarLoop]: 45 mSDtfsCounter, 0 mSDsluCounter, 57 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 102 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-22 01:29:06,206 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 102 Invalid, 29 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-22 01:29:06,207 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 204 states. [2024-11-22 01:29:06,258 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 204 to 204. [2024-11-22 01:29:06,259 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 204 states, 137 states have (on average 1.1897810218978102) internal successors, (163), 140 states have internal predecessors, (163), 42 states have call successors, (42), 25 states have call predecessors, (42), 24 states have return successors, (40), 38 states have call predecessors, (40), 40 states have call successors, (40) [2024-11-22 01:29:06,261 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 204 states to 204 states and 245 transitions. [2024-11-22 01:29:06,261 INFO L78 Accepts]: Start accepts. Automaton has 204 states and 245 transitions. Word has length 74 [2024-11-22 01:29:06,261 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:29:06,262 INFO L471 AbstractCegarLoop]: Abstraction has 204 states and 245 transitions. [2024-11-22 01:29:06,262 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), 4 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-22 01:29:06,262 INFO L276 IsEmpty]: Start isEmpty. Operand 204 states and 245 transitions. [2024-11-22 01:29:06,263 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 77 [2024-11-22 01:29:06,263 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:29:06,263 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:29:06,271 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-11-22 01:29:06,463 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,SelfDestructingSolverStorable13 [2024-11-22 01:29:06,464 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:29:06,464 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:29:06,464 INFO L85 PathProgramCache]: Analyzing trace with hash 224462768, now seen corresponding path program 1 times [2024-11-22 01:29:06,465 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:29:06,465 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [602397283] [2024-11-22 01:29:06,465 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:29:06,465 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:29:06,478 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:29:06,732 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 22 proven. 11 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2024-11-22 01:29:06,732 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:29:06,732 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [602397283] [2024-11-22 01:29:06,732 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [602397283] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-22 01:29:06,732 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [465100122] [2024-11-22 01:29:06,732 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:29:06,732 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:29:06,732 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:29:06,735 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-22 01:29:06,737 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-22 01:29:06,784 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:29:06,785 INFO L255 TraceCheckSpWp]: Trace formula consists of 182 conjuncts, 21 conjuncts are in the unsatisfiable core [2024-11-22 01:29:06,787 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:29:07,146 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 22 proven. 11 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2024-11-22 01:29:07,146 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-22 01:29:07,611 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 22 proven. 11 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2024-11-22 01:29:07,611 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [465100122] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-22 01:29:07,611 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-22 01:29:07,612 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 10, 8] total 17 [2024-11-22 01:29:07,612 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [567955729] [2024-11-22 01:29:07,612 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-22 01:29:07,612 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-22 01:29:07,612 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:29:07,613 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-22 01:29:07,613 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=52, Invalid=220, Unknown=0, NotChecked=0, Total=272 [2024-11-22 01:29:07,613 INFO L87 Difference]: Start difference. First operand 204 states and 245 transitions. Second operand has 17 states, 17 states have (on average 2.8823529411764706) internal successors, (49), 15 states have internal predecessors, (49), 9 states have call successors, (30), 3 states have call predecessors, (30), 1 states have return successors, (28), 9 states have call predecessors, (28), 9 states have call successors, (28) [2024-11-22 01:29:07,921 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:29:07,922 INFO L93 Difference]: Finished difference Result 218 states and 265 transitions. [2024-11-22 01:29:07,922 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-22 01:29:07,922 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 2.8823529411764706) internal successors, (49), 15 states have internal predecessors, (49), 9 states have call successors, (30), 3 states have call predecessors, (30), 1 states have return successors, (28), 9 states have call predecessors, (28), 9 states have call successors, (28) Word has length 76 [2024-11-22 01:29:07,922 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:29:07,925 INFO L225 Difference]: With dead ends: 218 [2024-11-22 01:29:07,925 INFO L226 Difference]: Without dead ends: 193 [2024-11-22 01:29:07,925 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 162 GetRequests, 142 SyntacticMatches, 1 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 67 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=83, Invalid=337, Unknown=0, NotChecked=0, Total=420 [2024-11-22 01:29:07,926 INFO L432 NwaCegarLoop]: 47 mSDtfsCounter, 34 mSDsluCounter, 243 mSDsCounter, 0 mSdLazyCounter, 123 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 43 SdHoareTripleChecker+Valid, 290 SdHoareTripleChecker+Invalid, 141 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 123 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-22 01:29:07,927 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [43 Valid, 290 Invalid, 141 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 123 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-22 01:29:07,928 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 193 states. [2024-11-22 01:29:07,969 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 193 to 185. [2024-11-22 01:29:07,970 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 185 states, 124 states have (on average 1.2016129032258065) internal successors, (149), 127 states have internal predecessors, (149), 38 states have call successors, (38), 23 states have call predecessors, (38), 22 states have return successors, (36), 34 states have call predecessors, (36), 36 states have call successors, (36) [2024-11-22 01:29:07,971 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 185 states to 185 states and 223 transitions. [2024-11-22 01:29:07,971 INFO L78 Accepts]: Start accepts. Automaton has 185 states and 223 transitions. Word has length 76 [2024-11-22 01:29:07,971 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:29:07,971 INFO L471 AbstractCegarLoop]: Abstraction has 185 states and 223 transitions. [2024-11-22 01:29:07,972 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 2.8823529411764706) internal successors, (49), 15 states have internal predecessors, (49), 9 states have call successors, (30), 3 states have call predecessors, (30), 1 states have return successors, (28), 9 states have call predecessors, (28), 9 states have call successors, (28) [2024-11-22 01:29:07,972 INFO L276 IsEmpty]: Start isEmpty. Operand 185 states and 223 transitions. [2024-11-22 01:29:07,974 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 81 [2024-11-22 01:29:07,975 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:29:07,975 INFO L215 NwaCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:29:07,995 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-22 01:29:08,175 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,SelfDestructingSolverStorable14 [2024-11-22 01:29:08,176 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:29:08,176 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:29:08,176 INFO L85 PathProgramCache]: Analyzing trace with hash 1653644173, now seen corresponding path program 1 times [2024-11-22 01:29:08,176 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:29:08,176 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [690491940] [2024-11-22 01:29:08,176 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:29:08,177 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:29:08,186 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:29:08,272 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 30 proven. 12 refuted. 0 times theorem prover too weak. 264 trivial. 0 not checked. [2024-11-22 01:29:08,272 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:29:08,272 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [690491940] [2024-11-22 01:29:08,273 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [690491940] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-22 01:29:08,273 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1119250513] [2024-11-22 01:29:08,273 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:29:08,273 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:29:08,273 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:29:08,275 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-22 01:29:08,277 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-22 01:29:08,325 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:29:08,327 INFO L255 TraceCheckSpWp]: Trace formula consists of 186 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-22 01:29:08,328 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:29:08,368 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 84 proven. 0 refuted. 0 times theorem prover too weak. 222 trivial. 0 not checked. [2024-11-22 01:29:08,369 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-22 01:29:08,369 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1119250513] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-22 01:29:08,369 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-22 01:29:08,369 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [5] total 6 [2024-11-22 01:29:08,369 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [81500529] [2024-11-22 01:29:08,370 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-22 01:29:08,370 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-22 01:29:08,370 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:29:08,372 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-22 01:29:08,372 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2024-11-22 01:29:08,372 INFO L87 Difference]: Start difference. First operand 185 states and 223 transitions. Second operand has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 4 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-11-22 01:29:08,460 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:29:08,460 INFO L93 Difference]: Finished difference Result 206 states and 249 transitions. [2024-11-22 01:29:08,461 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-22 01:29:08,461 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 4 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 80 [2024-11-22 01:29:08,461 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:29:08,462 INFO L225 Difference]: With dead ends: 206 [2024-11-22 01:29:08,463 INFO L226 Difference]: Without dead ends: 186 [2024-11-22 01:29:08,463 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 84 GetRequests, 80 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2024-11-22 01:29:08,464 INFO L432 NwaCegarLoop]: 47 mSDtfsCounter, 14 mSDsluCounter, 53 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 100 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-22 01:29:08,464 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 100 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-22 01:29:08,465 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 186 states. [2024-11-22 01:29:08,504 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 186 to 178. [2024-11-22 01:29:08,504 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 178 states, 120 states have (on average 1.175) internal successors, (141), 122 states have internal predecessors, (141), 36 states have call successors, (36), 21 states have call predecessors, (36), 21 states have return successors, (35), 34 states have call predecessors, (35), 35 states have call successors, (35) [2024-11-22 01:29:08,505 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 178 states to 178 states and 212 transitions. [2024-11-22 01:29:08,506 INFO L78 Accepts]: Start accepts. Automaton has 178 states and 212 transitions. Word has length 80 [2024-11-22 01:29:08,506 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:29:08,506 INFO L471 AbstractCegarLoop]: Abstraction has 178 states and 212 transitions. [2024-11-22 01:29:08,506 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 4 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-11-22 01:29:08,506 INFO L276 IsEmpty]: Start isEmpty. Operand 178 states and 212 transitions. [2024-11-22 01:29:08,507 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 90 [2024-11-22 01:29:08,507 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:29:08,507 INFO L215 NwaCegarLoop]: trace histogram [14, 13, 13, 5, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:29:08,516 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2024-11-22 01:29:08,708 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,SelfDestructingSolverStorable15 [2024-11-22 01:29:08,708 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:29:08,708 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:29:08,708 INFO L85 PathProgramCache]: Analyzing trace with hash 31903523, now seen corresponding path program 2 times [2024-11-22 01:29:08,709 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:29:08,709 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [336504751] [2024-11-22 01:29:08,709 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-22 01:29:08,709 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:29:08,726 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-22 01:29:08,727 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-22 01:29:08,859 INFO L134 CoverageAnalysis]: Checked inductivity of 382 backedges. 26 proven. 44 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2024-11-22 01:29:08,860 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:29:08,860 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [336504751] [2024-11-22 01:29:08,860 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [336504751] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-22 01:29:08,860 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [719342250] [2024-11-22 01:29:08,860 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-22 01:29:08,861 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:29:08,861 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:29:08,863 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-22 01:29:08,865 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-22 01:29:08,921 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-22 01:29:08,922 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-22 01:29:08,923 INFO L255 TraceCheckSpWp]: Trace formula consists of 212 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-22 01:29:08,925 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:29:09,030 INFO L134 CoverageAnalysis]: Checked inductivity of 382 backedges. 72 proven. 260 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2024-11-22 01:29:09,030 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-22 01:29:09,145 INFO L134 CoverageAnalysis]: Checked inductivity of 382 backedges. 26 proven. 44 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2024-11-22 01:29:09,145 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [719342250] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-22 01:29:09,145 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-22 01:29:09,145 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7, 8] total 8 [2024-11-22 01:29:09,145 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [556109347] [2024-11-22 01:29:09,145 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-22 01:29:09,146 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-22 01:29:09,146 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:29:09,146 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-22 01:29:09,146 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=33, Unknown=0, NotChecked=0, Total=56 [2024-11-22 01:29:09,147 INFO L87 Difference]: Start difference. First operand 178 states and 212 transitions. Second operand has 8 states, 8 states have (on average 5.0) internal successors, (40), 8 states have internal predecessors, (40), 5 states have call successors, (27), 6 states have call predecessors, (27), 6 states have return successors, (26), 5 states have call predecessors, (26), 5 states have call successors, (26) [2024-11-22 01:29:09,279 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:29:09,279 INFO L93 Difference]: Finished difference Result 248 states and 308 transitions. [2024-11-22 01:29:09,280 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-22 01:29:09,280 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 5.0) internal successors, (40), 8 states have internal predecessors, (40), 5 states have call successors, (27), 6 states have call predecessors, (27), 6 states have return successors, (26), 5 states have call predecessors, (26), 5 states have call successors, (26) Word has length 89 [2024-11-22 01:29:09,280 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:29:09,281 INFO L225 Difference]: With dead ends: 248 [2024-11-22 01:29:09,281 INFO L226 Difference]: Without dead ends: 180 [2024-11-22 01:29:09,282 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 188 GetRequests, 172 SyntacticMatches, 6 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=51, Invalid=81, Unknown=0, NotChecked=0, Total=132 [2024-11-22 01:29:09,283 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 10 mSDsluCounter, 102 mSDsCounter, 0 mSdLazyCounter, 58 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 133 SdHoareTripleChecker+Invalid, 59 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 58 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-22 01:29:09,283 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 133 Invalid, 59 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 58 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-22 01:29:09,284 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 180 states. [2024-11-22 01:29:09,326 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 180 to 180. [2024-11-22 01:29:09,326 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 180 states, 122 states have (on average 1.1721311475409837) internal successors, (143), 124 states have internal predecessors, (143), 36 states have call successors, (36), 21 states have call predecessors, (36), 21 states have return successors, (35), 34 states have call predecessors, (35), 35 states have call successors, (35) [2024-11-22 01:29:09,327 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 180 states to 180 states and 214 transitions. [2024-11-22 01:29:09,328 INFO L78 Accepts]: Start accepts. Automaton has 180 states and 214 transitions. Word has length 89 [2024-11-22 01:29:09,328 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:29:09,328 INFO L471 AbstractCegarLoop]: Abstraction has 180 states and 214 transitions. [2024-11-22 01:29:09,328 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 5.0) internal successors, (40), 8 states have internal predecessors, (40), 5 states have call successors, (27), 6 states have call predecessors, (27), 6 states have return successors, (26), 5 states have call predecessors, (26), 5 states have call successors, (26) [2024-11-22 01:29:09,329 INFO L276 IsEmpty]: Start isEmpty. Operand 180 states and 214 transitions. [2024-11-22 01:29:09,330 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2024-11-22 01:29:09,330 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:29:09,330 INFO L215 NwaCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:29:09,339 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-11-22 01:29:09,531 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,SelfDestructingSolverStorable16 [2024-11-22 01:29:09,531 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:29:09,531 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:29:09,532 INFO L85 PathProgramCache]: Analyzing trace with hash -1316865850, now seen corresponding path program 1 times [2024-11-22 01:29:09,532 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:29:09,532 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1895112444] [2024-11-22 01:29:09,532 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:29:09,532 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:29:09,562 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-22 01:29:09,563 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1104641341] [2024-11-22 01:29:09,564 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-22 01:29:09,564 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:29:09,564 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:29:09,570 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-22 01:29:09,571 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-22 01:29:09,630 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-22 01:29:09,637 INFO L255 TraceCheckSpWp]: Trace formula consists of 223 conjuncts, 45 conjuncts are in the unsatisfiable core [2024-11-22 01:29:09,640 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:29:10,632 INFO L134 CoverageAnalysis]: Checked inductivity of 366 backedges. 25 proven. 65 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2024-11-22 01:29:10,633 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-22 01:29:23,009 WARN L286 SmtUtils]: Spent 9.28s on a formula simplification that was a NOOP. DAG size: 138 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-22 01:29:54,341 INFO L134 CoverageAnalysis]: Checked inductivity of 366 backedges. 25 proven. 65 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2024-11-22 01:29:54,341 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:29:54,341 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1895112444] [2024-11-22 01:29:54,342 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-22 01:29:54,342 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1104641341] [2024-11-22 01:29:54,342 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1104641341] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-22 01:29:54,342 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-22 01:29:54,342 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 25 [2024-11-22 01:29:54,342 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1386749377] [2024-11-22 01:29:54,342 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-22 01:29:54,343 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2024-11-22 01:29:54,343 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:29:54,344 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2024-11-22 01:29:54,344 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=94, Invalid=506, Unknown=0, NotChecked=0, Total=600 [2024-11-22 01:29:54,344 INFO L87 Difference]: Start difference. First operand 180 states and 214 transitions. Second operand has 25 states, 25 states have (on average 2.24) internal successors, (56), 23 states have internal predecessors, (56), 13 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 10 states have call predecessors, (26), 11 states have call successors, (26) [2024-11-22 01:29:56,605 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-22 01:29:56,606 INFO L93 Difference]: Finished difference Result 240 states and 306 transitions. [2024-11-22 01:29:56,606 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-11-22 01:29:56,607 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 25 states have (on average 2.24) internal successors, (56), 23 states have internal predecessors, (56), 13 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 10 states have call predecessors, (26), 11 states have call successors, (26) Word has length 92 [2024-11-22 01:29:56,607 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-22 01:29:56,609 INFO L225 Difference]: With dead ends: 240 [2024-11-22 01:29:56,609 INFO L226 Difference]: Without dead ends: 216 [2024-11-22 01:29:56,609 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 187 GetRequests, 159 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 125 ImplicationChecksByTransitivity, 13.4s TimeCoverageRelationStatistics Valid=141, Invalid=729, Unknown=0, NotChecked=0, Total=870 [2024-11-22 01:29:56,610 INFO L432 NwaCegarLoop]: 47 mSDtfsCounter, 38 mSDsluCounter, 440 mSDsCounter, 0 mSdLazyCounter, 489 mSolverCounterSat, 66 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 42 SdHoareTripleChecker+Valid, 487 SdHoareTripleChecker+Invalid, 555 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 66 IncrementalHoareTripleChecker+Valid, 489 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.3s IncrementalHoareTripleChecker+Time [2024-11-22 01:29:56,611 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [42 Valid, 487 Invalid, 555 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [66 Valid, 489 Invalid, 0 Unknown, 0 Unchecked, 1.3s Time] [2024-11-22 01:29:56,612 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 216 states. [2024-11-22 01:29:56,673 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 216 to 192. [2024-11-22 01:29:56,673 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 192 states, 129 states have (on average 1.186046511627907) internal successors, (153), 132 states have internal predecessors, (153), 41 states have call successors, (41), 21 states have call predecessors, (41), 21 states have return successors, (40), 38 states have call predecessors, (40), 40 states have call successors, (40) [2024-11-22 01:29:56,676 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 192 states to 192 states and 234 transitions. [2024-11-22 01:29:56,677 INFO L78 Accepts]: Start accepts. Automaton has 192 states and 234 transitions. Word has length 92 [2024-11-22 01:29:56,679 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-22 01:29:56,679 INFO L471 AbstractCegarLoop]: Abstraction has 192 states and 234 transitions. [2024-11-22 01:29:56,679 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 25 states have (on average 2.24) internal successors, (56), 23 states have internal predecessors, (56), 13 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 10 states have call predecessors, (26), 11 states have call successors, (26) [2024-11-22 01:29:56,679 INFO L276 IsEmpty]: Start isEmpty. Operand 192 states and 234 transitions. [2024-11-22 01:29:56,681 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2024-11-22 01:29:56,681 INFO L207 NwaCegarLoop]: Found error trace [2024-11-22 01:29:56,681 INFO L215 NwaCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2024-11-22 01:29:56,691 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2024-11-22 01:29:56,885 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,SelfDestructingSolverStorable17 [2024-11-22 01:29:56,886 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-22 01:29:56,886 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-22 01:29:56,886 INFO L85 PathProgramCache]: Analyzing trace with hash -1315137972, now seen corresponding path program 3 times [2024-11-22 01:29:56,886 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-22 01:29:56,886 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [762322266] [2024-11-22 01:29:56,886 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-22 01:29:56,887 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-22 01:29:56,942 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2024-11-22 01:29:56,943 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-22 01:29:57,100 INFO L134 CoverageAnalysis]: Checked inductivity of 368 backedges. 54 proven. 2 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2024-11-22 01:29:57,100 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-22 01:29:57,100 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [762322266] [2024-11-22 01:29:57,100 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [762322266] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-22 01:29:57,100 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1303123337] [2024-11-22 01:29:57,100 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-22 01:29:57,101 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-22 01:29:57,101 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-22 01:29:57,103 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-22 01:29:57,104 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-11-22 01:29:57,168 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2024-11-22 01:29:57,168 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-22 01:29:57,170 INFO L255 TraceCheckSpWp]: Trace formula consists of 172 conjuncts, 48 conjuncts are in the unsatisfiable core [2024-11-22 01:29:57,173 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-22 01:29:57,823 INFO L134 CoverageAnalysis]: Checked inductivity of 368 backedges. 37 proven. 55 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2024-11-22 01:29:57,823 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-22 01:30:12,460 INFO L134 CoverageAnalysis]: Checked inductivity of 368 backedges. 37 proven. 55 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2024-11-22 01:30:12,460 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1303123337] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-22 01:30:12,460 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-22 01:30:12,461 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 14, 12] total 30 [2024-11-22 01:30:12,461 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1520740933] [2024-11-22 01:30:12,461 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-22 01:30:12,461 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2024-11-22 01:30:12,462 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-22 01:30:12,462 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2024-11-22 01:30:12,463 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=113, Invalid=757, Unknown=0, NotChecked=0, Total=870 [2024-11-22 01:30:12,463 INFO L87 Difference]: Start difference. First operand 192 states and 234 transitions. Second operand has 30 states, 30 states have (on average 2.7666666666666666) internal successors, (83), 29 states have internal predecessors, (83), 17 states have call successors, (42), 4 states have call predecessors, (42), 2 states have return successors, (39), 14 states have call predecessors, (39), 14 states have call successors, (39)