./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/dijkstra-u_unwindbound100.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 023d838f Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/dijkstra-u_unwindbound100.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 376367d14f0ef5deff3321a7267050cf9f2383eb99d0a19dad6a556c0772ff28 --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.fs.icfgbuilder-eval-023d838-m [2024-11-09 22:29:36,540 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-09 22:29:36,605 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-09 22:29:36,610 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-09 22:29:36,610 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-09 22:29:36,633 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-09 22:29:36,633 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-09 22:29:36,634 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-09 22:29:36,634 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-09 22:29:36,637 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-09 22:29:36,637 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-09 22:29:36,637 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-09 22:29:36,638 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-09 22:29:36,638 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-09 22:29:36,638 INFO L153 SettingsManager]: * Use SBE=true [2024-11-09 22:29:36,638 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-09 22:29:36,639 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-09 22:29:36,639 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-09 22:29:36,639 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-09 22:29:36,639 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-09 22:29:36,639 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-09 22:29:36,640 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-09 22:29:36,640 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-09 22:29:36,640 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-09 22:29:36,641 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-09 22:29:36,641 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-09 22:29:36,641 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-09 22:29:36,641 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-09 22:29:36,641 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2024-11-09 22:29:36,642 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-09 22:29:36,642 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-09 22:29:36,642 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-09 22:29:36,642 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-09 22:29:36,642 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-09 22:29:36,643 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-09 22:29:36,643 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-09 22:29:36,643 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-09 22:29:36,643 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-09 22:29:36,643 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-09 22:29:36,643 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-09 22:29:36,643 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-09 22:29:36,645 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-09 22:29:36,646 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 -> 376367d14f0ef5deff3321a7267050cf9f2383eb99d0a19dad6a556c0772ff28 [2024-11-09 22:29:36,845 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-09 22:29:36,865 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-09 22:29:36,868 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-09 22:29:36,869 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-09 22:29:36,869 INFO L274 PluginConnector]: CDTParser initialized [2024-11-09 22:29:36,870 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/dijkstra-u_unwindbound100.c [2024-11-09 22:29:38,120 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-09 22:29:38,257 INFO L384 CDTParser]: Found 1 translation units. [2024-11-09 22:29:38,258 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/dijkstra-u_unwindbound100.c [2024-11-09 22:29:38,265 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/d0859141e/e1b3d35093ec411d93018826db9e1f9e/FLAG60ab538b4 [2024-11-09 22:29:38,279 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/d0859141e/e1b3d35093ec411d93018826db9e1f9e [2024-11-09 22:29:38,283 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-09 22:29:38,285 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-09 22:29:38,286 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-09 22:29:38,287 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-09 22:29:38,291 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-09 22:29:38,292 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 10:29:38" (1/1) ... [2024-11-09 22:29:38,292 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@54b22b0e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:29:38, skipping insertion in model container [2024-11-09 22:29:38,294 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 10:29:38" (1/1) ... [2024-11-09 22:29:38,311 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-09 22:29:38,449 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/dijkstra-u_unwindbound100.c[525,538] [2024-11-09 22:29:38,484 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 22:29:38,493 INFO L200 MainTranslator]: Completed pre-run [2024-11-09 22:29:38,504 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/dijkstra-u_unwindbound100.c[525,538] [2024-11-09 22:29:38,514 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 22:29:38,531 INFO L204 MainTranslator]: Completed translation [2024-11-09 22:29:38,531 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:29:38 WrapperNode [2024-11-09 22:29:38,531 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-09 22:29:38,532 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-09 22:29:38,532 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-09 22:29:38,532 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-09 22:29:38,538 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:29:38" (1/1) ... [2024-11-09 22:29:38,545 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:29:38" (1/1) ... [2024-11-09 22:29:38,561 INFO L138 Inliner]: procedures = 14, calls = 17, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 62 [2024-11-09 22:29:38,563 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-09 22:29:38,564 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-09 22:29:38,564 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-09 22:29:38,564 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-09 22:29:38,571 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:29:38" (1/1) ... [2024-11-09 22:29:38,572 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:29:38" (1/1) ... [2024-11-09 22:29:38,577 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:29:38" (1/1) ... [2024-11-09 22:29:38,590 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-11-09 22:29:38,590 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:29:38" (1/1) ... [2024-11-09 22:29:38,590 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:29:38" (1/1) ... [2024-11-09 22:29:38,593 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:29:38" (1/1) ... [2024-11-09 22:29:38,593 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:29:38" (1/1) ... [2024-11-09 22:29:38,594 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:29:38" (1/1) ... [2024-11-09 22:29:38,597 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:29:38" (1/1) ... [2024-11-09 22:29:38,599 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-09 22:29:38,599 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2024-11-09 22:29:38,600 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2024-11-09 22:29:38,600 INFO L274 PluginConnector]: IcfgBuilder initialized [2024-11-09 22:29:38,600 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:29:38" (1/1) ... [2024-11-09 22:29:38,604 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-09 22:29:38,613 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:29:38,624 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-09 22:29:38,626 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-09 22:29:38,659 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-09 22:29:38,659 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-09 22:29:38,660 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-09 22:29:38,660 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-09 22:29:38,660 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-09 22:29:38,660 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-09 22:29:38,705 INFO L256 CfgBuilder]: Building ICFG [2024-11-09 22:29:38,707 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-09 22:29:38,853 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2024-11-09 22:29:38,853 INFO L307 CfgBuilder]: Performing block encoding [2024-11-09 22:29:38,863 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-09 22:29:38,863 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-09 22:29:38,863 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 09.11 10:29:38 BoogieIcfgContainer [2024-11-09 22:29:38,863 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2024-11-09 22:29:38,868 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-09 22:29:38,868 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-09 22:29:38,871 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-09 22:29:38,872 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 09.11 10:29:38" (1/3) ... [2024-11-09 22:29:38,873 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1f3f88a7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 10:29:38, skipping insertion in model container [2024-11-09 22:29:38,873 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:29:38" (2/3) ... [2024-11-09 22:29:38,874 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1f3f88a7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 10:29:38, skipping insertion in model container [2024-11-09 22:29:38,874 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 09.11 10:29:38" (3/3) ... [2024-11-09 22:29:38,875 INFO L112 eAbstractionObserver]: Analyzing ICFG dijkstra-u_unwindbound100.c [2024-11-09 22:29:38,887 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-09 22:29:38,887 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-09 22:29:38,936 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-09 22:29:38,945 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;@771f3988, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-09 22:29:38,945 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-09 22:29:38,949 INFO L276 IsEmpty]: Start isEmpty. Operand has 31 states, 19 states have (on average 1.5263157894736843) internal successors, (29), 20 states have internal predecessors, (29), 9 states have call successors, (9), 1 states have call predecessors, (9), 1 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-09 22:29:38,955 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2024-11-09 22:29:38,955 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:29:38,956 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:29:38,956 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:29:38,961 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:29:38,961 INFO L85 PathProgramCache]: Analyzing trace with hash 621682870, now seen corresponding path program 1 times [2024-11-09 22:29:38,968 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:29:38,968 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [891023119] [2024-11-09 22:29:38,968 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:29:38,968 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:29:39,039 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:29:39,098 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 22:29:39,100 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:29:39,100 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [891023119] [2024-11-09 22:29:39,101 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [891023119] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:29:39,101 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:29:39,111 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-09 22:29:39,113 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1869806573] [2024-11-09 22:29:39,113 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:29:39,117 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-09 22:29:39,118 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:29:39,136 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-09 22:29:39,136 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-09 22:29:39,138 INFO L87 Difference]: Start difference. First operand has 31 states, 19 states have (on average 1.5263157894736843) internal successors, (29), 20 states have internal predecessors, (29), 9 states have call successors, (9), 1 states have call predecessors, (9), 1 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 22:29:39,152 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:29:39,153 INFO L93 Difference]: Finished difference Result 59 states and 99 transitions. [2024-11-09 22:29:39,153 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-09 22:29:39,154 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 11 [2024-11-09 22:29:39,154 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:29:39,159 INFO L225 Difference]: With dead ends: 59 [2024-11-09 22:29:39,159 INFO L226 Difference]: Without dead ends: 27 [2024-11-09 22:29:39,161 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-09 22:29:39,163 INFO L432 NwaCegarLoop]: 43 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, 43 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-09 22:29:39,164 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 43 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 22:29:39,175 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2024-11-09 22:29:39,187 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2024-11-09 22:29:39,188 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 16 states have (on average 1.375) internal successors, (22), 17 states have internal predecessors, (22), 9 states have call successors, (9), 1 states have call predecessors, (9), 1 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-09 22:29:39,189 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 39 transitions. [2024-11-09 22:29:39,191 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 39 transitions. Word has length 11 [2024-11-09 22:29:39,191 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:29:39,191 INFO L471 AbstractCegarLoop]: Abstraction has 27 states and 39 transitions. [2024-11-09 22:29:39,191 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 22:29:39,191 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 39 transitions. [2024-11-09 22:29:39,192 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2024-11-09 22:29:39,192 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:29:39,192 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:29:39,193 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-09 22:29:39,193 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:29:39,193 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:29:39,193 INFO L85 PathProgramCache]: Analyzing trace with hash -770397230, now seen corresponding path program 1 times [2024-11-09 22:29:39,193 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:29:39,194 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [480671774] [2024-11-09 22:29:39,194 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:29:39,194 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:29:39,206 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:29:39,287 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 22:29:39,287 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:29:39,287 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [480671774] [2024-11-09 22:29:39,287 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [480671774] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:29:39,288 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:29:39,288 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-09 22:29:39,288 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [109816835] [2024-11-09 22:29:39,288 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:29:39,289 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-09 22:29:39,290 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:29:39,290 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-09 22:29:39,290 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-09 22:29:39,290 INFO L87 Difference]: Start difference. First operand 27 states and 39 transitions. Second operand has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 22:29:39,313 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:29:39,313 INFO L93 Difference]: Finished difference Result 49 states and 72 transitions. [2024-11-09 22:29:39,315 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-09 22:29:39,315 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 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 13 [2024-11-09 22:29:39,315 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:29:39,316 INFO L225 Difference]: With dead ends: 49 [2024-11-09 22:29:39,316 INFO L226 Difference]: Without dead ends: 29 [2024-11-09 22:29:39,316 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-09 22:29:39,317 INFO L432 NwaCegarLoop]: 37 mSDtfsCounter, 0 mSDsluCounter, 67 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 104 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-09 22:29:39,318 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 104 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 22:29:39,318 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2024-11-09 22:29:39,322 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 29. [2024-11-09 22:29:39,322 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 9 states have call successors, (9), 1 states have call predecessors, (9), 1 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-09 22:29:39,323 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 41 transitions. [2024-11-09 22:29:39,323 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 41 transitions. Word has length 13 [2024-11-09 22:29:39,323 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:29:39,323 INFO L471 AbstractCegarLoop]: Abstraction has 29 states and 41 transitions. [2024-11-09 22:29:39,324 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 22:29:39,324 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 41 transitions. [2024-11-09 22:29:39,324 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2024-11-09 22:29:39,324 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:29:39,324 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:29:39,324 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-09 22:29:39,325 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:29:39,325 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:29:39,325 INFO L85 PathProgramCache]: Analyzing trace with hash 1963862612, now seen corresponding path program 1 times [2024-11-09 22:29:39,325 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:29:39,325 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [48272162] [2024-11-09 22:29:39,325 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:29:39,326 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:29:39,350 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:29:39,454 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 22:29:39,455 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:29:39,456 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [48272162] [2024-11-09 22:29:39,456 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [48272162] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:29:39,456 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:29:39,456 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-09 22:29:39,456 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [118824145] [2024-11-09 22:29:39,456 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:29:39,457 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 22:29:39,457 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:29:39,457 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 22:29:39,459 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-11-09 22:29:39,459 INFO L87 Difference]: Start difference. First operand 29 states and 41 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, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 22:29:39,479 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:29:39,480 INFO L93 Difference]: Finished difference Result 43 states and 58 transitions. [2024-11-09 22:29:39,480 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 22:29:39,480 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, (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 14 [2024-11-09 22:29:39,480 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:29:39,481 INFO L225 Difference]: With dead ends: 43 [2024-11-09 22:29:39,481 INFO L226 Difference]: Without dead ends: 33 [2024-11-09 22:29:39,481 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 1 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-09 22:29:39,482 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 1 mSDsluCounter, 69 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 105 SdHoareTripleChecker+Invalid, 12 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-09 22:29:39,482 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 105 Invalid, 12 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 22:29:39,483 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2024-11-09 22:29:39,486 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 32. [2024-11-09 22:29:39,486 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 21 states have (on average 1.3333333333333333) internal successors, (28), 22 states have internal predecessors, (28), 9 states have call successors, (9), 1 states have call predecessors, (9), 1 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-09 22:29:39,487 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 45 transitions. [2024-11-09 22:29:39,487 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 45 transitions. Word has length 14 [2024-11-09 22:29:39,487 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:29:39,487 INFO L471 AbstractCegarLoop]: Abstraction has 32 states and 45 transitions. [2024-11-09 22:29:39,487 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, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 22:29:39,487 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 45 transitions. [2024-11-09 22:29:39,488 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2024-11-09 22:29:39,488 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:29:39,488 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:29:39,488 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-11-09 22:29:39,488 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:29:39,488 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:29:39,489 INFO L85 PathProgramCache]: Analyzing trace with hash 2003574015, now seen corresponding path program 1 times [2024-11-09 22:29:39,489 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:29:39,489 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1271494878] [2024-11-09 22:29:39,489 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:29:39,489 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:29:39,510 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:29:39,787 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 22:29:39,787 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:29:39,787 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1271494878] [2024-11-09 22:29:39,787 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1271494878] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:29:39,787 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:29:39,787 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-09 22:29:39,788 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1385439522] [2024-11-09 22:29:39,788 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:29:39,788 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-09 22:29:39,788 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:29:39,788 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-09 22:29:39,789 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-11-09 22:29:39,789 INFO L87 Difference]: Start difference. First operand 32 states and 45 transitions. Second operand has 6 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 5 states have internal predecessors, (13), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 22:29:39,964 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:29:39,964 INFO L93 Difference]: Finished difference Result 63 states and 93 transitions. [2024-11-09 22:29:39,965 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-09 22:29:39,965 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 5 states have internal predecessors, (13), 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 14 [2024-11-09 22:29:39,965 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:29:39,966 INFO L225 Difference]: With dead ends: 63 [2024-11-09 22:29:39,966 INFO L226 Difference]: Without dead ends: 43 [2024-11-09 22:29:39,966 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-09 22:29:39,967 INFO L432 NwaCegarLoop]: 43 mSDtfsCounter, 6 mSDsluCounter, 139 mSDsCounter, 0 mSdLazyCounter, 52 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 182 SdHoareTripleChecker+Invalid, 65 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 52 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 22:29:39,967 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 182 Invalid, 65 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 52 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 22:29:39,968 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2024-11-09 22:29:39,982 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 43. [2024-11-09 22:29:39,983 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 25 states have (on average 1.28) internal successors, (32), 26 states have internal predecessors, (32), 15 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2024-11-09 22:29:39,985 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 61 transitions. [2024-11-09 22:29:39,985 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 61 transitions. Word has length 14 [2024-11-09 22:29:39,985 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:29:39,985 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 61 transitions. [2024-11-09 22:29:39,985 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 5 states have internal predecessors, (13), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 22:29:39,985 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 61 transitions. [2024-11-09 22:29:39,986 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2024-11-09 22:29:39,986 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:29:39,986 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:29:39,986 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2024-11-09 22:29:39,986 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:29:39,986 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:29:39,986 INFO L85 PathProgramCache]: Analyzing trace with hash 2027361748, now seen corresponding path program 1 times [2024-11-09 22:29:39,986 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:29:39,987 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1199239966] [2024-11-09 22:29:39,987 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:29:39,987 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:29:40,002 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:29:40,048 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 22:29:40,048 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:29:40,048 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1199239966] [2024-11-09 22:29:40,049 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1199239966] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 22:29:40,049 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1354819103] [2024-11-09 22:29:40,049 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:29:40,050 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:29:40,050 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:29:40,051 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:29:40,053 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-09 22:29:40,093 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:29:40,096 INFO L255 TraceCheckSpWp]: Trace formula consists of 64 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-09 22:29:40,099 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:29:40,134 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 22:29:40,135 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:29:40,169 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 22:29:40,169 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1354819103] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:29:40,170 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 22:29:40,170 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4, 4] total 7 [2024-11-09 22:29:40,170 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1419538191] [2024-11-09 22:29:40,170 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 22:29:40,170 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-09 22:29:40,170 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:29:40,171 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-09 22:29:40,174 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2024-11-09 22:29:40,174 INFO L87 Difference]: Start difference. First operand 43 states and 61 transitions. Second operand has 8 states, 8 states have (on average 3.0) internal successors, (24), 7 states have internal predecessors, (24), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 22:29:41,487 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.27s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:29:41,630 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:29:41,630 INFO L93 Difference]: Finished difference Result 102 states and 146 transitions. [2024-11-09 22:29:41,630 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-09 22:29:41,630 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.0) internal successors, (24), 7 states have internal predecessors, (24), 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 16 [2024-11-09 22:29:41,631 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:29:41,631 INFO L225 Difference]: With dead ends: 102 [2024-11-09 22:29:41,631 INFO L226 Difference]: Without dead ends: 82 [2024-11-09 22:29:41,632 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 37 GetRequests, 28 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-09 22:29:41,632 INFO L432 NwaCegarLoop]: 44 mSDtfsCounter, 66 mSDsluCounter, 123 mSDsCounter, 0 mSdLazyCounter, 82 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 66 SdHoareTripleChecker+Valid, 167 SdHoareTripleChecker+Invalid, 98 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 82 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.4s IncrementalHoareTripleChecker+Time [2024-11-09 22:29:41,633 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [66 Valid, 167 Invalid, 98 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 82 Invalid, 0 Unknown, 0 Unchecked, 1.4s Time] [2024-11-09 22:29:41,633 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2024-11-09 22:29:41,641 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 58. [2024-11-09 22:29:41,642 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 36 states have (on average 1.2777777777777777) internal successors, (46), 38 states have internal predecessors, (46), 18 states have call successors, (18), 3 states have call predecessors, (18), 3 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2024-11-09 22:29:41,643 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 80 transitions. [2024-11-09 22:29:41,643 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 80 transitions. Word has length 16 [2024-11-09 22:29:41,643 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:29:41,644 INFO L471 AbstractCegarLoop]: Abstraction has 58 states and 80 transitions. [2024-11-09 22:29:41,644 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.0) internal successors, (24), 7 states have internal predecessors, (24), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 22:29:41,644 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 80 transitions. [2024-11-09 22:29:41,644 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2024-11-09 22:29:41,644 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:29:41,644 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:29:41,657 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-09 22:29:41,845 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-09 22:29:41,846 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:29:41,847 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:29:41,847 INFO L85 PathProgramCache]: Analyzing trace with hash -1499922286, now seen corresponding path program 1 times [2024-11-09 22:29:41,847 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:29:41,847 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2029347425] [2024-11-09 22:29:41,847 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:29:41,847 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:29:41,858 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:29:41,903 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 22:29:41,904 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:29:41,904 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2029347425] [2024-11-09 22:29:41,904 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2029347425] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 22:29:41,904 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1028902502] [2024-11-09 22:29:41,904 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:29:41,904 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:29:41,904 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:29:41,907 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:29:41,909 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-09 22:29:41,945 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:29:41,945 INFO L255 TraceCheckSpWp]: Trace formula consists of 65 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 22:29:41,946 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:29:41,967 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 22:29:41,967 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:29:42,015 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 22:29:42,016 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1028902502] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:29:42,016 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 22:29:42,016 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 5] total 9 [2024-11-09 22:29:42,016 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1276052149] [2024-11-09 22:29:42,016 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 22:29:42,016 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-09 22:29:42,016 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:29:42,017 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-09 22:29:42,017 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2024-11-09 22:29:42,017 INFO L87 Difference]: Start difference. First operand 58 states and 80 transitions. Second operand has 10 states, 10 states have (on average 2.8) internal successors, (28), 9 states have internal predecessors, (28), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 22:29:46,108 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:29:47,171 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.04s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2024-11-09 22:29:51,827 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:29:51,846 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:29:51,847 INFO L93 Difference]: Finished difference Result 138 states and 194 transitions. [2024-11-09 22:29:51,847 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-09 22:29:51,847 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.8) internal successors, (28), 9 states have internal predecessors, (28), 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 17 [2024-11-09 22:29:51,847 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:29:51,850 INFO L225 Difference]: With dead ends: 138 [2024-11-09 22:29:51,851 INFO L226 Difference]: Without dead ends: 128 [2024-11-09 22:29:51,851 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 29 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=63, Invalid=119, Unknown=0, NotChecked=0, Total=182 [2024-11-09 22:29:51,852 INFO L432 NwaCegarLoop]: 44 mSDtfsCounter, 134 mSDsluCounter, 202 mSDsCounter, 0 mSdLazyCounter, 114 mSolverCounterSat, 41 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 9.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 134 SdHoareTripleChecker+Valid, 246 SdHoareTripleChecker+Invalid, 157 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 41 IncrementalHoareTripleChecker+Valid, 114 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 9.8s IncrementalHoareTripleChecker+Time [2024-11-09 22:29:51,852 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [134 Valid, 246 Invalid, 157 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [41 Valid, 114 Invalid, 2 Unknown, 0 Unchecked, 9.8s Time] [2024-11-09 22:29:51,852 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 128 states. [2024-11-09 22:29:51,863 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 128 to 115. [2024-11-09 22:29:51,863 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 115 states, 63 states have (on average 1.3492063492063493) internal successors, (85), 68 states have internal predecessors, (85), 45 states have call successors, (45), 6 states have call predecessors, (45), 6 states have return successors, (40), 40 states have call predecessors, (40), 40 states have call successors, (40) [2024-11-09 22:29:51,864 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 115 states to 115 states and 170 transitions. [2024-11-09 22:29:51,865 INFO L78 Accepts]: Start accepts. Automaton has 115 states and 170 transitions. Word has length 17 [2024-11-09 22:29:51,865 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:29:51,865 INFO L471 AbstractCegarLoop]: Abstraction has 115 states and 170 transitions. [2024-11-09 22:29:51,865 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.8) internal successors, (28), 9 states have internal predecessors, (28), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 22:29:51,865 INFO L276 IsEmpty]: Start isEmpty. Operand 115 states and 170 transitions. [2024-11-09 22:29:51,865 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2024-11-09 22:29:51,866 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:29:51,866 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:29:51,879 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-09 22:29:52,070 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2024-11-09 22:29:52,071 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:29:52,071 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:29:52,071 INFO L85 PathProgramCache]: Analyzing trace with hash -1460210883, now seen corresponding path program 1 times [2024-11-09 22:29:52,071 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:29:52,071 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [683462509] [2024-11-09 22:29:52,071 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:29:52,072 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:29:52,086 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:29:52,241 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-09 22:29:52,241 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:29:52,241 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [683462509] [2024-11-09 22:29:52,241 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [683462509] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:29:52,242 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:29:52,242 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-09 22:29:52,242 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1098411289] [2024-11-09 22:29:52,242 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:29:52,242 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-09 22:29:52,242 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:29:52,242 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-09 22:29:52,242 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-11-09 22:29:52,242 INFO L87 Difference]: Start difference. First operand 115 states and 170 transitions. Second operand has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 22:29:56,296 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:29:56,993 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:29:56,993 INFO L93 Difference]: Finished difference Result 207 states and 316 transitions. [2024-11-09 22:29:56,994 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-09 22:29:56,994 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 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 17 [2024-11-09 22:29:56,994 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:29:56,995 INFO L225 Difference]: With dead ends: 207 [2024-11-09 22:29:56,996 INFO L226 Difference]: Without dead ends: 204 [2024-11-09 22:29:56,996 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-09 22:29:56,997 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 14 mSDsluCounter, 114 mSDsCounter, 0 mSdLazyCounter, 62 mSolverCounterSat, 16 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 150 SdHoareTripleChecker+Invalid, 79 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 62 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.7s IncrementalHoareTripleChecker+Time [2024-11-09 22:29:56,997 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 150 Invalid, 79 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 62 Invalid, 1 Unknown, 0 Unchecked, 4.7s Time] [2024-11-09 22:29:56,998 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 204 states. [2024-11-09 22:29:57,029 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 204 to 142. [2024-11-09 22:29:57,032 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 142 states, 83 states have (on average 1.2771084337349397) internal successors, (106), 91 states have internal predecessors, (106), 48 states have call successors, (48), 10 states have call predecessors, (48), 10 states have return successors, (43), 40 states have call predecessors, (43), 43 states have call successors, (43) [2024-11-09 22:29:57,033 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 142 states to 142 states and 197 transitions. [2024-11-09 22:29:57,034 INFO L78 Accepts]: Start accepts. Automaton has 142 states and 197 transitions. Word has length 17 [2024-11-09 22:29:57,034 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:29:57,034 INFO L471 AbstractCegarLoop]: Abstraction has 142 states and 197 transitions. [2024-11-09 22:29:57,034 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 22:29:57,034 INFO L276 IsEmpty]: Start isEmpty. Operand 142 states and 197 transitions. [2024-11-09 22:29:57,034 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2024-11-09 22:29:57,036 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:29:57,036 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:29:57,036 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2024-11-09 22:29:57,036 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:29:57,037 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:29:57,037 INFO L85 PathProgramCache]: Analyzing trace with hash 752431267, now seen corresponding path program 1 times [2024-11-09 22:29:57,037 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:29:57,037 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [130327677] [2024-11-09 22:29:57,037 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:29:57,037 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:29:57,051 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:29:57,054 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [340130814] [2024-11-09 22:29:57,054 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:29:57,054 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:29:57,054 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:29:57,056 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:29:57,057 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-09 22:29:57,093 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:29:57,093 INFO L255 TraceCheckSpWp]: Trace formula consists of 66 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-09 22:29:57,094 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:29:57,198 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 22:29:57,199 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 22:29:57,199 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:29:57,199 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [130327677] [2024-11-09 22:29:57,199 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:29:57,200 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [340130814] [2024-11-09 22:29:57,200 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [340130814] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:29:57,200 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:29:57,200 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-09 22:29:57,200 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [331658843] [2024-11-09 22:29:57,200 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:29:57,200 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-09 22:29:57,200 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:29:57,201 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-09 22:29:57,201 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-09 22:29:57,201 INFO L87 Difference]: Start difference. First operand 142 states and 197 transitions. Second operand has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-09 22:30:01,302 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:30:01,358 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:30:01,358 INFO L93 Difference]: Finished difference Result 149 states and 203 transitions. [2024-11-09 22:30:01,358 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-09 22:30:01,359 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 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 19 [2024-11-09 22:30:01,359 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:30:01,361 INFO L225 Difference]: With dead ends: 149 [2024-11-09 22:30:01,361 INFO L226 Difference]: Without dead ends: 146 [2024-11-09 22:30:01,361 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2024-11-09 22:30:01,362 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 3 mSDsluCounter, 107 mSDsCounter, 0 mSdLazyCounter, 57 mSolverCounterSat, 4 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 136 SdHoareTripleChecker+Invalid, 62 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 57 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.1s IncrementalHoareTripleChecker+Time [2024-11-09 22:30:01,362 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 136 Invalid, 62 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 57 Invalid, 1 Unknown, 0 Unchecked, 4.1s Time] [2024-11-09 22:30:01,362 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 146 states. [2024-11-09 22:30:01,384 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 146 to 146. [2024-11-09 22:30:01,385 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 146 states, 86 states have (on average 1.2674418604651163) internal successors, (109), 94 states have internal predecessors, (109), 48 states have call successors, (48), 11 states have call predecessors, (48), 11 states have return successors, (43), 40 states have call predecessors, (43), 43 states have call successors, (43) [2024-11-09 22:30:01,387 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 146 states to 146 states and 200 transitions. [2024-11-09 22:30:01,389 INFO L78 Accepts]: Start accepts. Automaton has 146 states and 200 transitions. Word has length 19 [2024-11-09 22:30:01,389 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:30:01,389 INFO L471 AbstractCegarLoop]: Abstraction has 146 states and 200 transitions. [2024-11-09 22:30:01,389 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-09 22:30:01,389 INFO L276 IsEmpty]: Start isEmpty. Operand 146 states and 200 transitions. [2024-11-09 22:30:01,390 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2024-11-09 22:30:01,391 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:30:01,391 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:30:01,411 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-09 22:30:01,591 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-09 22:30:01,592 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:30:01,593 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:30:01,593 INFO L85 PathProgramCache]: Analyzing trace with hash -126840539, now seen corresponding path program 1 times [2024-11-09 22:30:01,593 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:30:01,593 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [131249646] [2024-11-09 22:30:01,593 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:30:01,593 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:30:01,607 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:30:01,608 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [323637268] [2024-11-09 22:30:01,608 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:30:01,608 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:30:01,608 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:30:01,613 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:30:01,616 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-09 22:30:01,695 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:30:01,696 INFO L255 TraceCheckSpWp]: Trace formula consists of 74 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-09 22:30:01,697 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:30:01,795 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 22:30:01,796 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:30:01,983 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 22:30:01,983 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:30:01,983 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [131249646] [2024-11-09 22:30:01,983 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:30:01,983 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [323637268] [2024-11-09 22:30:01,983 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [323637268] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:30:01,983 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 22:30:01,983 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2024-11-09 22:30:01,983 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1829812345] [2024-11-09 22:30:01,983 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 22:30:01,984 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-09 22:30:01,984 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:30:01,987 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-09 22:30:01,987 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-09 22:30:01,988 INFO L87 Difference]: Start difference. First operand 146 states and 200 transitions. Second operand has 8 states, 8 states have (on average 3.5) internal successors, (28), 7 states have internal predecessors, (28), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-09 22:30:10,658 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:30:14,771 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:30:18,778 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:30:23,563 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:30:29,775 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:30:33,794 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:30:37,798 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:30:42,353 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:30:46,416 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:30:50,951 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:30:50,969 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:30:50,969 INFO L93 Difference]: Finished difference Result 226 states and 322 transitions. [2024-11-09 22:30:50,969 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-09 22:30:50,970 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.5) internal successors, (28), 7 states have internal predecessors, (28), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 22 [2024-11-09 22:30:50,970 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:30:50,971 INFO L225 Difference]: With dead ends: 226 [2024-11-09 22:30:50,971 INFO L226 Difference]: Without dead ends: 179 [2024-11-09 22:30:50,972 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 44 GetRequests, 34 SyntacticMatches, 2 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 4.8s TimeCoverageRelationStatistics Valid=27, Invalid=62, Unknown=1, NotChecked=0, Total=90 [2024-11-09 22:30:50,972 INFO L432 NwaCegarLoop]: 47 mSDtfsCounter, 15 mSDsluCounter, 155 mSDsCounter, 0 mSdLazyCounter, 117 mSolverCounterSat, 52 mSolverCounterUnsat, 10 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 44.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 202 SdHoareTripleChecker+Invalid, 179 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 52 IncrementalHoareTripleChecker+Valid, 117 IncrementalHoareTripleChecker+Invalid, 10 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 44.3s IncrementalHoareTripleChecker+Time [2024-11-09 22:30:50,972 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [31 Valid, 202 Invalid, 179 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [52 Valid, 117 Invalid, 10 Unknown, 0 Unchecked, 44.3s Time] [2024-11-09 22:30:50,973 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 179 states. [2024-11-09 22:30:50,994 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 179 to 174. [2024-11-09 22:30:50,995 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 174 states, 98 states have (on average 1.2244897959183674) internal successors, (120), 105 states have internal predecessors, (120), 61 states have call successors, (61), 14 states have call predecessors, (61), 14 states have return successors, (57), 54 states have call predecessors, (57), 57 states have call successors, (57) [2024-11-09 22:30:50,996 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 174 states to 174 states and 238 transitions. [2024-11-09 22:30:50,996 INFO L78 Accepts]: Start accepts. Automaton has 174 states and 238 transitions. Word has length 22 [2024-11-09 22:30:50,996 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:30:50,996 INFO L471 AbstractCegarLoop]: Abstraction has 174 states and 238 transitions. [2024-11-09 22:30:50,996 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.5) internal successors, (28), 7 states have internal predecessors, (28), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-09 22:30:50,996 INFO L276 IsEmpty]: Start isEmpty. Operand 174 states and 238 transitions. [2024-11-09 22:30:50,997 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2024-11-09 22:30:50,997 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:30:50,997 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:30:51,007 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-09 22:30:51,197 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-09 22:30:51,198 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:30:51,198 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:30:51,198 INFO L85 PathProgramCache]: Analyzing trace with hash 1408557887, now seen corresponding path program 1 times [2024-11-09 22:30:51,198 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:30:51,198 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [106542936] [2024-11-09 22:30:51,198 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:30:51,198 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:30:51,206 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:30:51,206 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [110174079] [2024-11-09 22:30:51,206 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:30:51,206 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:30:51,207 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:30:51,208 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:30:51,209 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-09 22:30:51,246 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:30:51,247 INFO L255 TraceCheckSpWp]: Trace formula consists of 75 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 22:30:51,248 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:30:51,297 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-09 22:30:51,297 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 22:30:51,297 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:30:51,297 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [106542936] [2024-11-09 22:30:51,298 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:30:51,298 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [110174079] [2024-11-09 22:30:51,298 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [110174079] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:30:51,298 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:30:51,298 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 22:30:51,298 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1998916070] [2024-11-09 22:30:51,298 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:30:51,298 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 22:30:51,298 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:30:51,298 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 22:30:51,298 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 22:30:51,299 INFO L87 Difference]: Start difference. First operand 174 states and 238 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, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-09 22:30:55,376 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:30:55,395 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:30:55,395 INFO L93 Difference]: Finished difference Result 223 states and 300 transitions. [2024-11-09 22:30:55,396 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 22:30:55,396 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, (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 24 [2024-11-09 22:30:55,397 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:30:55,398 INFO L225 Difference]: With dead ends: 223 [2024-11-09 22:30:55,398 INFO L226 Difference]: Without dead ends: 214 [2024-11-09 22:30:55,398 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-09 22:30:55,399 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 7 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 33 mSolverCounterSat, 3 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 37 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 33 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.1s IncrementalHoareTripleChecker+Time [2024-11-09 22:30:55,399 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 124 Invalid, 37 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 33 Invalid, 1 Unknown, 0 Unchecked, 4.1s Time] [2024-11-09 22:30:55,399 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 214 states. [2024-11-09 22:30:55,424 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 214 to 214. [2024-11-09 22:30:55,425 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 214 states, 122 states have (on average 1.1967213114754098) internal successors, (146), 129 states have internal predecessors, (146), 72 states have call successors, (72), 20 states have call predecessors, (72), 19 states have return successors, (65), 64 states have call predecessors, (65), 65 states have call successors, (65) [2024-11-09 22:30:55,426 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 214 states to 214 states and 283 transitions. [2024-11-09 22:30:55,426 INFO L78 Accepts]: Start accepts. Automaton has 214 states and 283 transitions. Word has length 24 [2024-11-09 22:30:55,426 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:30:55,426 INFO L471 AbstractCegarLoop]: Abstraction has 214 states and 283 transitions. [2024-11-09 22:30:55,426 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, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-09 22:30:55,426 INFO L276 IsEmpty]: Start isEmpty. Operand 214 states and 283 transitions. [2024-11-09 22:30:55,429 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2024-11-09 22:30:55,429 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:30:55,429 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:30:55,441 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-09 22:30:55,629 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-11-09 22:30:55,630 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:30:55,630 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:30:55,630 INFO L85 PathProgramCache]: Analyzing trace with hash 1709334525, now seen corresponding path program 1 times [2024-11-09 22:30:55,630 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:30:55,630 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [342722014] [2024-11-09 22:30:55,631 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:30:55,631 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:30:55,636 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:30:55,705 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 22:30:55,705 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:30:55,705 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [342722014] [2024-11-09 22:30:55,705 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [342722014] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 22:30:55,705 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [588952252] [2024-11-09 22:30:55,705 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:30:55,705 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:30:55,705 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:30:55,706 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:30:55,707 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-09 22:30:55,735 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:30:55,736 INFO L255 TraceCheckSpWp]: Trace formula consists of 88 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-09 22:30:55,737 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:30:55,761 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 22:30:55,761 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:30:55,839 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 22:30:55,840 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [588952252] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:30:55,840 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 22:30:55,840 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 13 [2024-11-09 22:30:55,840 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1615549956] [2024-11-09 22:30:55,840 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 22:30:55,840 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-09 22:30:55,840 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:30:55,848 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-09 22:30:55,849 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2024-11-09 22:30:55,849 INFO L87 Difference]: Start difference. First operand 214 states and 283 transitions. Second operand has 14 states, 14 states have (on average 3.0) internal successors, (42), 13 states have internal predecessors, (42), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 22:31:00,014 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:31:04,125 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:31:08,139 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:31:10,327 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.68s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:31:14,491 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:31:18,563 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2024-11-09 22:31:19,289 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:31:19,289 INFO L93 Difference]: Finished difference Result 426 states and 585 transitions. [2024-11-09 22:31:19,289 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-11-09 22:31:19,289 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 3.0) internal successors, (42), 13 states have internal predecessors, (42), 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 25 [2024-11-09 22:31:19,290 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:31:19,291 INFO L225 Difference]: With dead ends: 426 [2024-11-09 22:31:19,291 INFO L226 Difference]: Without dead ends: 389 [2024-11-09 22:31:19,292 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 64 GetRequests, 43 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 55 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=184, Invalid=322, Unknown=0, NotChecked=0, Total=506 [2024-11-09 22:31:19,292 INFO L432 NwaCegarLoop]: 49 mSDtfsCounter, 304 mSDsluCounter, 248 mSDsCounter, 0 mSdLazyCounter, 199 mSolverCounterSat, 122 mSolverCounterUnsat, 5 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 23.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 304 SdHoareTripleChecker+Valid, 297 SdHoareTripleChecker+Invalid, 326 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 122 IncrementalHoareTripleChecker+Valid, 199 IncrementalHoareTripleChecker+Invalid, 5 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 23.3s IncrementalHoareTripleChecker+Time [2024-11-09 22:31:19,292 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [304 Valid, 297 Invalid, 326 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [122 Valid, 199 Invalid, 5 Unknown, 0 Unchecked, 23.3s Time] [2024-11-09 22:31:19,293 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 389 states. [2024-11-09 22:31:19,323 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 389 to 365. [2024-11-09 22:31:19,323 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 365 states, 193 states have (on average 1.2487046632124352) internal successors, (241), 208 states have internal predecessors, (241), 140 states have call successors, (140), 32 states have call predecessors, (140), 31 states have return successors, (125), 124 states have call predecessors, (125), 125 states have call successors, (125) [2024-11-09 22:31:19,325 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 365 states to 365 states and 506 transitions. [2024-11-09 22:31:19,326 INFO L78 Accepts]: Start accepts. Automaton has 365 states and 506 transitions. Word has length 25 [2024-11-09 22:31:19,326 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:31:19,326 INFO L471 AbstractCegarLoop]: Abstraction has 365 states and 506 transitions. [2024-11-09 22:31:19,326 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 3.0) internal successors, (42), 13 states have internal predecessors, (42), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 22:31:19,326 INFO L276 IsEmpty]: Start isEmpty. Operand 365 states and 506 transitions. [2024-11-09 22:31:19,329 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2024-11-09 22:31:19,329 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:31:19,329 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:31:19,341 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-11-09 22:31:19,530 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:31:19,531 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:31:19,531 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:31:19,531 INFO L85 PathProgramCache]: Analyzing trace with hash -1261317597, now seen corresponding path program 2 times [2024-11-09 22:31:19,531 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:31:19,531 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1186586108] [2024-11-09 22:31:19,531 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:31:19,531 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:31:19,546 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:31:19,547 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [768458533] [2024-11-09 22:31:19,547 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-09 22:31:19,547 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:31:19,547 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:31:19,553 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:31:19,554 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-09 22:31:19,634 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-09 22:31:19,634 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 22:31:19,635 INFO L255 TraceCheckSpWp]: Trace formula consists of 98 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-09 22:31:19,636 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:31:19,798 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 2 proven. 30 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 22:31:19,799 INFO L311 TraceCheckSpWp]: Computing backward predicates...