/usr/lib/jvm/java-1.11.0-openjdk-amd64/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data -s ../../../trunk/examples/settings/default/automizer/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.use.bitabs.translation false -tc ../../../trunk/examples/toolchains/AutomizerCInline.xml -i ../../../trunk/examples/svcomp/recursified_nla-digbench/recursified_egcd3-ll.c -------------------------------------------------------------------------------- This is Ultimate 0.2.4-tmp.fs.bitabs-eval-d9c3e40-m [2023-12-16 05:53:04,240 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-12-16 05:53:04,299 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/default/automizer/svcomp-Reach-32bit-Automizer_Default.epf [2023-12-16 05:53:04,303 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-12-16 05:53:04,303 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-12-16 05:53:04,330 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-12-16 05:53:04,331 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-12-16 05:53:04,331 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-12-16 05:53:04,332 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2023-12-16 05:53:04,334 INFO L153 SettingsManager]: * Use memory slicer=true [2023-12-16 05:53:04,335 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-12-16 05:53:04,335 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-12-16 05:53:04,335 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2023-12-16 05:53:04,336 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2023-12-16 05:53:04,337 INFO L153 SettingsManager]: * Use SBE=true [2023-12-16 05:53:04,337 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-12-16 05:53:04,337 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-12-16 05:53:04,337 INFO L153 SettingsManager]: * sizeof long=4 [2023-12-16 05:53:04,337 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-12-16 05:53:04,337 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-12-16 05:53:04,337 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-12-16 05:53:04,338 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-12-16 05:53:04,338 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-12-16 05:53:04,338 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-12-16 05:53:04,338 INFO L153 SettingsManager]: * Allow undefined functions=false [2023-12-16 05:53:04,338 INFO L153 SettingsManager]: * sizeof long double=12 [2023-12-16 05:53:04,339 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-12-16 05:53:04,339 INFO L153 SettingsManager]: * Use constant arrays=true [2023-12-16 05:53:04,339 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-12-16 05:53:04,339 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2023-12-16 05:53:04,340 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2023-12-16 05:53:04,340 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-12-16 05:53:04,340 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2023-12-16 05:53:04,340 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-12-16 05:53:04,341 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-12-16 05:53:04,341 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-12-16 05:53:04,341 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2023-12-16 05:53:04,341 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-12-16 05:53:04,341 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2023-12-16 05:53:04,341 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2023-12-16 05:53:04,341 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-12-16 05:53:04,341 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2023-12-16 05:53:04,341 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-12-16 05:53:04,342 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: Use bitabs translation -> false [2023-12-16 05:53:04,540 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-12-16 05:53:04,557 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-12-16 05:53:04,559 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-12-16 05:53:04,559 INFO L270 PluginConnector]: Initializing CDTParser... [2023-12-16 05:53:04,560 INFO L274 PluginConnector]: CDTParser initialized [2023-12-16 05:53:04,560 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/recursified_nla-digbench/recursified_egcd3-ll.c [2023-12-16 05:53:05,665 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-12-16 05:53:05,809 INFO L384 CDTParser]: Found 1 translation units. [2023-12-16 05:53:05,809 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/recursified_nla-digbench/recursified_egcd3-ll.c [2023-12-16 05:53:05,814 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/c194dbed9/0990237c082d4f5898a01108fe04b4db/FLAGe2f793d07 [2023-12-16 05:53:05,825 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/c194dbed9/0990237c082d4f5898a01108fe04b4db [2023-12-16 05:53:05,827 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-12-16 05:53:05,828 INFO L133 ToolchainWalker]: Walking toolchain with 5 elements. [2023-12-16 05:53:05,830 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-12-16 05:53:05,830 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-12-16 05:53:05,833 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-12-16 05:53:05,833 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.12 05:53:05" (1/1) ... [2023-12-16 05:53:05,834 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@3c19b383 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 05:53:05, skipping insertion in model container [2023-12-16 05:53:05,834 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.12 05:53:05" (1/1) ... [2023-12-16 05:53:05,861 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-12-16 05:53:05,980 WARN L239 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/recursified_nla-digbench/recursified_egcd3-ll.c[1052,1065] [2023-12-16 05:53:06,002 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-12-16 05:53:06,018 INFO L202 MainTranslator]: Completed pre-run [2023-12-16 05:53:06,028 WARN L239 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/recursified_nla-digbench/recursified_egcd3-ll.c[1052,1065] [2023-12-16 05:53:06,056 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-12-16 05:53:06,076 INFO L206 MainTranslator]: Completed translation [2023-12-16 05:53:06,077 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 05:53:06 WrapperNode [2023-12-16 05:53:06,077 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-12-16 05:53:06,078 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-12-16 05:53:06,078 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-12-16 05:53:06,078 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-12-16 05:53:06,083 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 05:53:06" (1/1) ... [2023-12-16 05:53:06,100 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 05:53:06" (1/1) ... [2023-12-16 05:53:06,138 INFO L138 Inliner]: procedures = 18, calls = 127, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 95 [2023-12-16 05:53:06,138 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-12-16 05:53:06,139 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-12-16 05:53:06,139 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-12-16 05:53:06,139 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-12-16 05:53:06,147 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 05:53:06" (1/1) ... [2023-12-16 05:53:06,147 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 05:53:06" (1/1) ... [2023-12-16 05:53:06,164 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 05:53:06" (1/1) ... [2023-12-16 05:53:06,194 INFO L175 MemorySlicer]: Split 77 memory accesses to 13 slices as follows [2, 5, 6, 9, 7, 7, 7, 6, 6, 6, 5, 6, 5]. 12 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]. The 22 writes are split as follows [0, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2]. [2023-12-16 05:53:06,194 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 05:53:06" (1/1) ... [2023-12-16 05:53:06,194 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 05:53:06" (1/1) ... [2023-12-16 05:53:06,200 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 05:53:06" (1/1) ... [2023-12-16 05:53:06,202 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 05:53:06" (1/1) ... [2023-12-16 05:53:06,203 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 05:53:06" (1/1) ... [2023-12-16 05:53:06,216 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 05:53:06" (1/1) ... [2023-12-16 05:53:06,221 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-12-16 05:53:06,222 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-12-16 05:53:06,222 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-12-16 05:53:06,222 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-12-16 05:53:06,223 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 05:53:06" (1/1) ... [2023-12-16 05:53:06,228 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2023-12-16 05:53:06,238 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-16 05:53:06,287 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) [2023-12-16 05:53:06,316 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 [2023-12-16 05:53:06,334 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-12-16 05:53:06,334 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2023-12-16 05:53:06,334 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2023-12-16 05:53:06,334 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2023-12-16 05:53:06,334 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2023-12-16 05:53:06,334 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2023-12-16 05:53:06,334 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2023-12-16 05:53:06,335 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#4 [2023-12-16 05:53:06,335 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#5 [2023-12-16 05:53:06,335 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#6 [2023-12-16 05:53:06,335 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#7 [2023-12-16 05:53:06,335 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#8 [2023-12-16 05:53:06,335 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#9 [2023-12-16 05:53:06,335 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#10 [2023-12-16 05:53:06,335 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#11 [2023-12-16 05:53:06,335 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#12 [2023-12-16 05:53:06,335 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_47_to_56_0 [2023-12-16 05:53:06,335 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_47_to_56_0 [2023-12-16 05:53:06,336 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_33_to_70_0 [2023-12-16 05:53:06,336 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_33_to_70_0 [2023-12-16 05:53:06,336 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2023-12-16 05:53:06,336 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_40_to_59_0 [2023-12-16 05:53:06,336 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_40_to_59_0 [2023-12-16 05:53:06,336 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2023-12-16 05:53:06,336 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2023-12-16 05:53:06,336 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2023-12-16 05:53:06,336 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2023-12-16 05:53:06,336 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#4 [2023-12-16 05:53:06,336 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#5 [2023-12-16 05:53:06,336 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#6 [2023-12-16 05:53:06,337 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#7 [2023-12-16 05:53:06,337 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#8 [2023-12-16 05:53:06,337 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#9 [2023-12-16 05:53:06,337 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#10 [2023-12-16 05:53:06,337 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#11 [2023-12-16 05:53:06,337 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#12 [2023-12-16 05:53:06,337 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-12-16 05:53:06,337 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-12-16 05:53:06,337 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2023-12-16 05:53:06,337 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2023-12-16 05:53:06,337 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2023-12-16 05:53:06,337 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2023-12-16 05:53:06,337 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#4 [2023-12-16 05:53:06,337 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#5 [2023-12-16 05:53:06,338 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#6 [2023-12-16 05:53:06,338 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#7 [2023-12-16 05:53:06,338 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#8 [2023-12-16 05:53:06,338 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#9 [2023-12-16 05:53:06,338 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#10 [2023-12-16 05:53:06,338 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#11 [2023-12-16 05:53:06,338 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#12 [2023-12-16 05:53:06,338 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-12-16 05:53:06,338 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-12-16 05:53:06,338 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2023-12-16 05:53:06,493 INFO L241 CfgBuilder]: Building ICFG [2023-12-16 05:53:06,495 INFO L267 CfgBuilder]: Building CFG for each procedure with an implementation [2023-12-16 05:53:06,784 INFO L282 CfgBuilder]: Performing block encoding [2023-12-16 05:53:06,828 INFO L304 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-12-16 05:53:06,828 INFO L309 CfgBuilder]: Removed 3 assume(true) statements. [2023-12-16 05:53:06,828 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 16.12 05:53:06 BoogieIcfgContainer [2023-12-16 05:53:06,828 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-12-16 05:53:06,832 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-12-16 05:53:06,832 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-12-16 05:53:06,834 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-12-16 05:53:06,834 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 16.12 05:53:05" (1/3) ... [2023-12-16 05:53:06,835 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@504bf466 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.12 05:53:06, skipping insertion in model container [2023-12-16 05:53:06,835 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 05:53:06" (2/3) ... [2023-12-16 05:53:06,835 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@504bf466 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.12 05:53:06, skipping insertion in model container [2023-12-16 05:53:06,835 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 16.12 05:53:06" (3/3) ... [2023-12-16 05:53:06,838 INFO L112 eAbstractionObserver]: Analyzing ICFG recursified_egcd3-ll.c [2023-12-16 05:53:06,851 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-12-16 05:53:06,851 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-12-16 05:53:06,910 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-12-16 05:53:06,915 INFO L357 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, mHoare=true, 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;@687db52a, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-12-16 05:53:06,915 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-12-16 05:53:06,918 INFO L276 IsEmpty]: Start isEmpty. Operand has 50 states, 30 states have (on average 1.3) internal successors, (39), 34 states have internal predecessors, (39), 13 states have call successors, (13), 5 states have call predecessors, (13), 5 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2023-12-16 05:53:06,923 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2023-12-16 05:53:06,923 INFO L187 NwaCegarLoop]: Found error trace [2023-12-16 05:53:06,923 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-16 05:53:06,924 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-16 05:53:06,928 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-16 05:53:06,928 INFO L85 PathProgramCache]: Analyzing trace with hash 1622724067, now seen corresponding path program 1 times [2023-12-16 05:53:06,934 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-16 05:53:06,934 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1773382634] [2023-12-16 05:53:06,935 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-16 05:53:06,935 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-16 05:53:07,050 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-16 05:53:07,094 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-16 05:53:07,095 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1773382634] [2023-12-16 05:53:07,095 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unsupported non-linear arithmetic [2023-12-16 05:53:07,095 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [468485547] [2023-12-16 05:53:07,095 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-16 05:53:07,096 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-16 05:53:07,097 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-16 05:53:07,100 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) [2023-12-16 05:53:07,129 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-12-16 05:53:07,248 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-16 05:53:07,251 INFO L262 TraceCheckSpWp]: Trace formula consists of 279 conjuncts, 1 conjunts are in the unsatisfiable core [2023-12-16 05:53:07,255 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-16 05:53:07,273 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-12-16 05:53:07,273 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-16 05:53:07,274 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [468485547] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-16 05:53:07,275 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-16 05:53:07,275 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-12-16 05:53:07,278 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [155608739] [2023-12-16 05:53:07,278 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-16 05:53:07,281 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-12-16 05:53:07,282 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-16 05:53:07,299 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-12-16 05:53:07,299 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-12-16 05:53:07,301 INFO L87 Difference]: Start difference. First operand has 50 states, 30 states have (on average 1.3) internal successors, (39), 34 states have internal predecessors, (39), 13 states have call successors, (13), 5 states have call predecessors, (13), 5 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) Second operand has 2 states, 2 states have (on average 7.5) internal successors, (15), 2 states have internal predecessors, (15), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2023-12-16 05:53:07,326 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-16 05:53:07,326 INFO L93 Difference]: Finished difference Result 98 states and 140 transitions. [2023-12-16 05:53:07,327 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-12-16 05:53:07,327 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 7.5) internal successors, (15), 2 states have internal predecessors, (15), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) Word has length 23 [2023-12-16 05:53:07,328 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-16 05:53:07,332 INFO L225 Difference]: With dead ends: 98 [2023-12-16 05:53:07,332 INFO L226 Difference]: Without dead ends: 48 [2023-12-16 05:53:07,335 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-12-16 05:53:07,339 INFO L413 NwaCegarLoop]: 58 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 2 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 58 SdHoareTripleChecker+Invalid, 2 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 2 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-16 05:53:07,340 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 58 Invalid, 2 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 2 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-16 05:53:07,350 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2023-12-16 05:53:07,362 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 48. [2023-12-16 05:53:07,362 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 29 states have (on average 1.1379310344827587) internal successors, (33), 33 states have internal predecessors, (33), 13 states have call successors, (13), 5 states have call predecessors, (13), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2023-12-16 05:53:07,364 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 58 transitions. [2023-12-16 05:53:07,364 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 58 transitions. Word has length 23 [2023-12-16 05:53:07,365 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-16 05:53:07,365 INFO L495 AbstractCegarLoop]: Abstraction has 48 states and 58 transitions. [2023-12-16 05:53:07,365 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 7.5) internal successors, (15), 2 states have internal predecessors, (15), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2023-12-16 05:53:07,365 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 58 transitions. [2023-12-16 05:53:07,366 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2023-12-16 05:53:07,366 INFO L187 NwaCegarLoop]: Found error trace [2023-12-16 05:53:07,366 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-16 05:53:07,374 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2023-12-16 05:53:07,571 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2023-12-16 05:53:07,572 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-16 05:53:07,572 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-16 05:53:07,572 INFO L85 PathProgramCache]: Analyzing trace with hash 1864870065, now seen corresponding path program 1 times [2023-12-16 05:53:07,572 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-16 05:53:07,573 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [805299304] [2023-12-16 05:53:07,573 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-16 05:53:07,573 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-16 05:53:07,620 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-16 05:53:07,623 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [318251045] [2023-12-16 05:53:07,623 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-16 05:53:07,624 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-16 05:53:07,624 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-16 05:53:07,625 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) [2023-12-16 05:53:07,637 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-12-16 05:53:07,744 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-16 05:53:07,745 INFO L262 TraceCheckSpWp]: Trace formula consists of 282 conjuncts, 22 conjunts are in the unsatisfiable core [2023-12-16 05:53:07,749 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-16 05:53:07,852 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 15 [2023-12-16 05:53:07,860 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-16 05:53:07,952 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-12-16 05:53:07,953 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-16 05:53:07,956 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-16 05:53:07,956 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [805299304] [2023-12-16 05:53:07,956 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-16 05:53:07,956 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [318251045] [2023-12-16 05:53:07,956 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [318251045] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-16 05:53:07,957 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-16 05:53:07,957 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2023-12-16 05:53:07,957 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1253943624] [2023-12-16 05:53:07,957 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-16 05:53:07,957 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2023-12-16 05:53:07,957 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-16 05:53:07,958 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2023-12-16 05:53:07,959 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=105, Unknown=0, NotChecked=0, Total=132 [2023-12-16 05:53:07,959 INFO L87 Difference]: Start difference. First operand 48 states and 58 transitions. Second operand has 12 states, 10 states have (on average 1.7) internal successors, (17), 10 states have internal predecessors, (17), 4 states have call successors, (4), 3 states have call predecessors, (4), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2023-12-16 05:53:08,359 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-16 05:53:08,359 INFO L93 Difference]: Finished difference Result 58 states and 68 transitions. [2023-12-16 05:53:08,359 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2023-12-16 05:53:08,360 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 10 states have (on average 1.7) internal successors, (17), 10 states have internal predecessors, (17), 4 states have call successors, (4), 3 states have call predecessors, (4), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 24 [2023-12-16 05:53:08,360 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-16 05:53:08,361 INFO L225 Difference]: With dead ends: 58 [2023-12-16 05:53:08,362 INFO L226 Difference]: Without dead ends: 50 [2023-12-16 05:53:08,362 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 46 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=57, Invalid=249, Unknown=0, NotChecked=0, Total=306 [2023-12-16 05:53:08,363 INFO L413 NwaCegarLoop]: 10 mSDtfsCounter, 39 mSDsluCounter, 42 mSDsCounter, 0 mSdLazyCounter, 441 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 48 SdHoareTripleChecker+Valid, 52 SdHoareTripleChecker+Invalid, 448 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 441 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-12-16 05:53:08,363 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [48 Valid, 52 Invalid, 448 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 441 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-12-16 05:53:08,363 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2023-12-16 05:53:08,368 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 50. [2023-12-16 05:53:08,369 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 30 states have (on average 1.1333333333333333) internal successors, (34), 34 states have internal predecessors, (34), 13 states have call successors, (13), 5 states have call predecessors, (13), 6 states have return successors, (13), 12 states have call predecessors, (13), 12 states have call successors, (13) [2023-12-16 05:53:08,370 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 60 transitions. [2023-12-16 05:53:08,370 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 60 transitions. Word has length 24 [2023-12-16 05:53:08,370 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-16 05:53:08,370 INFO L495 AbstractCegarLoop]: Abstraction has 50 states and 60 transitions. [2023-12-16 05:53:08,370 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 10 states have (on average 1.7) internal successors, (17), 10 states have internal predecessors, (17), 4 states have call successors, (4), 3 states have call predecessors, (4), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2023-12-16 05:53:08,370 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 60 transitions. [2023-12-16 05:53:08,371 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2023-12-16 05:53:08,371 INFO L187 NwaCegarLoop]: Found error trace [2023-12-16 05:53:08,371 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-16 05:53:08,377 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-12-16 05:53:08,576 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable1 [2023-12-16 05:53:08,576 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-16 05:53:08,577 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-16 05:53:08,577 INFO L85 PathProgramCache]: Analyzing trace with hash -176414272, now seen corresponding path program 1 times [2023-12-16 05:53:08,577 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-16 05:53:08,577 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1823081581] [2023-12-16 05:53:08,577 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-16 05:53:08,577 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-16 05:53:08,623 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-16 05:53:08,624 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [883186042] [2023-12-16 05:53:08,624 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-16 05:53:08,624 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-16 05:53:08,624 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-16 05:53:08,628 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) [2023-12-16 05:53:08,633 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-12-16 05:53:08,791 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-16 05:53:08,795 INFO L262 TraceCheckSpWp]: Trace formula consists of 528 conjuncts, 139 conjunts are in the unsatisfiable core [2023-12-16 05:53:08,798 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-16 05:53:08,808 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-16 05:53:08,859 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-16 05:53:08,864 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-16 05:53:08,872 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-16 05:53:09,210 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-16 05:53:09,212 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2023-12-16 05:53:09,251 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-12-16 05:53:09,252 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-16 05:53:09,252 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-16 05:53:09,252 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1823081581] [2023-12-16 05:53:09,252 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-16 05:53:09,252 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [883186042] [2023-12-16 05:53:09,252 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [883186042] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-16 05:53:09,252 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-16 05:53:09,252 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [15] imperfect sequences [] total 15 [2023-12-16 05:53:09,252 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1087950776] [2023-12-16 05:53:09,252 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-16 05:53:09,253 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-12-16 05:53:09,253 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-16 05:53:09,253 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-12-16 05:53:09,253 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=182, Unknown=0, NotChecked=0, Total=210 [2023-12-16 05:53:09,253 INFO L87 Difference]: Start difference. First operand 50 states and 60 transitions. Second operand has 15 states, 13 states have (on average 1.5384615384615385) internal successors, (20), 11 states have internal predecessors, (20), 5 states have call successors, (6), 5 states have call predecessors, (6), 2 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2023-12-16 05:53:09,734 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-16 05:53:09,734 INFO L93 Difference]: Finished difference Result 85 states and 102 transitions. [2023-12-16 05:53:09,735 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2023-12-16 05:53:09,735 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 13 states have (on average 1.5384615384615385) internal successors, (20), 11 states have internal predecessors, (20), 5 states have call successors, (6), 5 states have call predecessors, (6), 2 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 28 [2023-12-16 05:53:09,735 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-16 05:53:09,736 INFO L225 Difference]: With dead ends: 85 [2023-12-16 05:53:09,736 INFO L226 Difference]: Without dead ends: 81 [2023-12-16 05:53:09,736 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 33 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 29 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=54, Invalid=366, Unknown=0, NotChecked=0, Total=420 [2023-12-16 05:53:09,737 INFO L413 NwaCegarLoop]: 37 mSDtfsCounter, 41 mSDsluCounter, 356 mSDsCounter, 0 mSdLazyCounter, 354 mSolverCounterSat, 20 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 393 SdHoareTripleChecker+Invalid, 374 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 20 IncrementalHoareTripleChecker+Valid, 354 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-12-16 05:53:09,737 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [41 Valid, 393 Invalid, 374 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [20 Valid, 354 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-12-16 05:53:09,738 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 81 states. [2023-12-16 05:53:09,746 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 81 to 80. [2023-12-16 05:53:09,747 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 80 states, 49 states have (on average 1.1224489795918366) internal successors, (55), 55 states have internal predecessors, (55), 21 states have call successors, (21), 9 states have call predecessors, (21), 9 states have return successors, (21), 19 states have call predecessors, (21), 20 states have call successors, (21) [2023-12-16 05:53:09,747 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 80 states to 80 states and 97 transitions. [2023-12-16 05:53:09,748 INFO L78 Accepts]: Start accepts. Automaton has 80 states and 97 transitions. Word has length 28 [2023-12-16 05:53:09,748 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-16 05:53:09,748 INFO L495 AbstractCegarLoop]: Abstraction has 80 states and 97 transitions. [2023-12-16 05:53:09,748 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 13 states have (on average 1.5384615384615385) internal successors, (20), 11 states have internal predecessors, (20), 5 states have call successors, (6), 5 states have call predecessors, (6), 2 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2023-12-16 05:53:09,748 INFO L276 IsEmpty]: Start isEmpty. Operand 80 states and 97 transitions. [2023-12-16 05:53:09,749 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2023-12-16 05:53:09,749 INFO L187 NwaCegarLoop]: Found error trace [2023-12-16 05:53:09,749 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-16 05:53:09,756 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-12-16 05:53:09,955 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-16 05:53:09,956 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-16 05:53:09,957 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-16 05:53:09,957 INFO L85 PathProgramCache]: Analyzing trace with hash -466915291, now seen corresponding path program 1 times [2023-12-16 05:53:09,957 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-16 05:53:09,957 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [245370778] [2023-12-16 05:53:09,957 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-16 05:53:09,957 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-16 05:53:09,990 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-16 05:53:09,990 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [101363324] [2023-12-16 05:53:09,990 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-16 05:53:09,990 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-16 05:53:09,990 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-16 05:53:09,991 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) [2023-12-16 05:53:10,006 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-12-16 05:53:10,164 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-16 05:53:10,168 INFO L262 TraceCheckSpWp]: Trace formula consists of 547 conjuncts, 211 conjunts are in the unsatisfiable core [2023-12-16 05:53:10,173 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-16 05:53:10,188 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-16 05:53:10,190 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-16 05:53:10,282 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-16 05:53:10,287 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-16 05:53:10,293 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-16 05:53:10,317 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-16 05:53:10,528 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-16 05:53:10,535 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 15 [2023-12-16 05:53:10,691 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-16 05:53:11,009 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-16 05:53:11,011 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 10 [2023-12-16 05:53:11,016 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2023-12-16 05:53:11,075 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 3 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-12-16 05:53:11,075 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-16 05:53:11,408 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-12-16 05:53:11,408 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-16 05:53:11,408 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [245370778] [2023-12-16 05:53:11,409 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-16 05:53:11,409 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [101363324] [2023-12-16 05:53:11,409 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [101363324] provided 1 perfect and 1 imperfect interpolant sequences [2023-12-16 05:53:11,409 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-12-16 05:53:11,409 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [20] total 30 [2023-12-16 05:53:11,409 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2060734977] [2023-12-16 05:53:11,409 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-16 05:53:11,409 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2023-12-16 05:53:11,409 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-16 05:53:11,410 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2023-12-16 05:53:11,410 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=83, Invalid=787, Unknown=0, NotChecked=0, Total=870 [2023-12-16 05:53:11,410 INFO L87 Difference]: Start difference. First operand 80 states and 97 transitions. Second operand has 12 states, 10 states have (on average 2.1) internal successors, (21), 8 states have internal predecessors, (21), 6 states have call successors, (7), 5 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2023-12-16 05:53:11,848 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-16 05:53:11,848 INFO L93 Difference]: Finished difference Result 87 states and 103 transitions. [2023-12-16 05:53:11,849 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2023-12-16 05:53:11,849 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 10 states have (on average 2.1) internal successors, (21), 8 states have internal predecessors, (21), 6 states have call successors, (7), 5 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 34 [2023-12-16 05:53:11,849 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-16 05:53:11,850 INFO L225 Difference]: With dead ends: 87 [2023-12-16 05:53:11,850 INFO L226 Difference]: Without dead ends: 85 [2023-12-16 05:53:11,850 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 71 GetRequests, 37 SyntacticMatches, 1 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 170 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=105, Invalid=1085, Unknown=0, NotChecked=0, Total=1190 [2023-12-16 05:53:11,851 INFO L413 NwaCegarLoop]: 42 mSDtfsCounter, 32 mSDsluCounter, 306 mSDsCounter, 0 mSdLazyCounter, 313 mSolverCounterSat, 19 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 348 SdHoareTripleChecker+Invalid, 332 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 313 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-12-16 05:53:11,851 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [32 Valid, 348 Invalid, 332 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 313 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-12-16 05:53:11,851 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 85 states. [2023-12-16 05:53:11,872 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 85 to 84. [2023-12-16 05:53:11,872 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 84 states, 52 states have (on average 1.1153846153846154) internal successors, (58), 58 states have internal predecessors, (58), 21 states have call successors, (21), 10 states have call predecessors, (21), 10 states have return successors, (21), 19 states have call predecessors, (21), 20 states have call successors, (21) [2023-12-16 05:53:11,876 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 84 states to 84 states and 100 transitions. [2023-12-16 05:53:11,876 INFO L78 Accepts]: Start accepts. Automaton has 84 states and 100 transitions. Word has length 34 [2023-12-16 05:53:11,876 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-16 05:53:11,876 INFO L495 AbstractCegarLoop]: Abstraction has 84 states and 100 transitions. [2023-12-16 05:53:11,876 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 10 states have (on average 2.1) internal successors, (21), 8 states have internal predecessors, (21), 6 states have call successors, (7), 5 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2023-12-16 05:53:11,876 INFO L276 IsEmpty]: Start isEmpty. Operand 84 states and 100 transitions. [2023-12-16 05:53:11,879 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2023-12-16 05:53:11,879 INFO L187 NwaCegarLoop]: Found error trace [2023-12-16 05:53:11,879 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-16 05:53:11,906 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-12-16 05:53:12,079 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-16 05:53:12,080 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-16 05:53:12,080 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-16 05:53:12,080 INFO L85 PathProgramCache]: Analyzing trace with hash 212011526, now seen corresponding path program 1 times [2023-12-16 05:53:12,080 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-16 05:53:12,080 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [8092880] [2023-12-16 05:53:12,080 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-16 05:53:12,080 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-16 05:53:12,129 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-16 05:53:12,129 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1320397683] [2023-12-16 05:53:12,129 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-16 05:53:12,129 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-16 05:53:12,129 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-16 05:53:12,132 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) [2023-12-16 05:53:12,156 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-12-16 05:53:12,315 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-16 05:53:12,317 INFO L262 TraceCheckSpWp]: Trace formula consists of 533 conjuncts, 39 conjunts are in the unsatisfiable core [2023-12-16 05:53:12,321 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-16 05:53:12,383 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-16 05:53:12,387 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-16 05:53:12,420 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-16 05:53:12,446 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 19 [2023-12-16 05:53:12,448 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-16 05:53:12,523 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-16 05:53:12,538 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 1 proven. 8 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-16 05:53:12,538 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-16 05:53:13,053 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-12-16 05:53:13,054 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-16 05:53:13,054 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [8092880] [2023-12-16 05:53:13,054 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-16 05:53:13,054 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1320397683] [2023-12-16 05:53:13,054 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1320397683] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-16 05:53:13,054 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-16 05:53:13,054 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 17] total 32 [2023-12-16 05:53:13,054 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [958920815] [2023-12-16 05:53:13,054 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-16 05:53:13,055 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 32 states [2023-12-16 05:53:13,055 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-16 05:53:13,055 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2023-12-16 05:53:13,055 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=98, Invalid=894, Unknown=0, NotChecked=0, Total=992 [2023-12-16 05:53:13,056 INFO L87 Difference]: Start difference. First operand 84 states and 100 transitions. Second operand has 32 states, 26 states have (on average 1.8076923076923077) internal successors, (47), 28 states have internal predecessors, (47), 11 states have call successors, (11), 9 states have call predecessors, (11), 9 states have return successors, (10), 6 states have call predecessors, (10), 10 states have call successors, (10) [2023-12-16 05:53:17,093 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-16 05:53:18,073 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-16 05:53:18,073 INFO L93 Difference]: Finished difference Result 104 states and 124 transitions. [2023-12-16 05:53:18,073 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2023-12-16 05:53:18,073 INFO L78 Accepts]: Start accepts. Automaton has has 32 states, 26 states have (on average 1.8076923076923077) internal successors, (47), 28 states have internal predecessors, (47), 11 states have call successors, (11), 9 states have call predecessors, (11), 9 states have return successors, (10), 6 states have call predecessors, (10), 10 states have call successors, (10) Word has length 37 [2023-12-16 05:53:18,074 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-16 05:53:18,075 INFO L225 Difference]: With dead ends: 104 [2023-12-16 05:53:18,075 INFO L226 Difference]: Without dead ends: 96 [2023-12-16 05:53:18,076 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 89 GetRequests, 41 SyntacticMatches, 2 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 311 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=298, Invalid=1958, Unknown=0, NotChecked=0, Total=2256 [2023-12-16 05:53:18,076 INFO L413 NwaCegarLoop]: 10 mSDtfsCounter, 164 mSDsluCounter, 66 mSDsCounter, 0 mSdLazyCounter, 946 mSolverCounterSat, 132 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 166 SdHoareTripleChecker+Valid, 76 SdHoareTripleChecker+Invalid, 1079 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 132 IncrementalHoareTripleChecker+Valid, 946 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.7s IncrementalHoareTripleChecker+Time [2023-12-16 05:53:18,077 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [166 Valid, 76 Invalid, 1079 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [132 Valid, 946 Invalid, 1 Unknown, 0 Unchecked, 4.7s Time] [2023-12-16 05:53:18,077 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 96 states. [2023-12-16 05:53:18,102 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 96 to 96. [2023-12-16 05:53:18,104 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 59 states have (on average 1.1016949152542372) internal successors, (65), 65 states have internal predecessors, (65), 22 states have call successors, (22), 11 states have call predecessors, (22), 14 states have return successors, (29), 21 states have call predecessors, (29), 21 states have call successors, (29) [2023-12-16 05:53:18,121 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 116 transitions. [2023-12-16 05:53:18,122 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 116 transitions. Word has length 37 [2023-12-16 05:53:18,123 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-16 05:53:18,123 INFO L495 AbstractCegarLoop]: Abstraction has 96 states and 116 transitions. [2023-12-16 05:53:18,123 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 32 states, 26 states have (on average 1.8076923076923077) internal successors, (47), 28 states have internal predecessors, (47), 11 states have call successors, (11), 9 states have call predecessors, (11), 9 states have return successors, (10), 6 states have call predecessors, (10), 10 states have call successors, (10) [2023-12-16 05:53:18,123 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 116 transitions. [2023-12-16 05:53:18,127 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2023-12-16 05:53:18,127 INFO L187 NwaCegarLoop]: Found error trace [2023-12-16 05:53:18,127 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-16 05:53:18,135 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-12-16 05:53:18,327 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-16 05:53:18,328 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-16 05:53:18,328 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-16 05:53:18,328 INFO L85 PathProgramCache]: Analyzing trace with hash 451765875, now seen corresponding path program 1 times [2023-12-16 05:53:18,328 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-16 05:53:18,328 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [393296533] [2023-12-16 05:53:18,328 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-16 05:53:18,329 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-16 05:53:18,366 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-16 05:53:18,366 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1823337915] [2023-12-16 05:53:18,366 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-16 05:53:18,366 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-16 05:53:18,367 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-16 05:53:18,370 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) [2023-12-16 05:53:18,372 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-12-16 05:53:18,634 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-16 05:53:18,640 INFO L262 TraceCheckSpWp]: Trace formula consists of 777 conjuncts, 276 conjunts are in the unsatisfiable core [2023-12-16 05:53:18,646 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-16 05:53:18,652 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-16 05:53:18,664 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-16 05:53:18,789 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-16 05:53:18,793 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-16 05:53:18,804 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-16 05:53:18,813 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-16 05:53:19,011 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-16 05:53:19,068 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-16 05:53:19,254 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-16 05:53:19,285 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-16 05:53:19,289 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-16 05:53:19,303 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 19 [2023-12-16 05:53:19,307 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 15 [2023-12-16 05:53:19,630 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-16 05:53:19,632 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2023-12-16 05:53:19,640 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2023-12-16 05:53:19,689 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 1 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-16 05:53:19,689 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-16 05:53:26,581 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-16 05:53:26,581 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [393296533] [2023-12-16 05:53:26,581 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-16 05:53:26,581 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1823337915] [2023-12-16 05:53:26,581 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1823337915] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-16 05:53:26,581 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-16 05:53:26,581 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22] total 22 [2023-12-16 05:53:26,582 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [853075753] [2023-12-16 05:53:26,582 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-16 05:53:26,582 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2023-12-16 05:53:26,582 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-16 05:53:26,582 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2023-12-16 05:53:26,583 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=88, Invalid=901, Unknown=3, NotChecked=0, Total=992 [2023-12-16 05:53:26,583 INFO L87 Difference]: Start difference. First operand 96 states and 116 transitions. Second operand has 22 states, 18 states have (on average 1.5555555555555556) internal successors, (28), 16 states have internal predecessors, (28), 7 states have call successors, (8), 8 states have call predecessors, (8), 3 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) [2023-12-16 05:53:30,630 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-16 05:53:32,547 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-16 05:53:32,547 INFO L93 Difference]: Finished difference Result 177 states and 213 transitions. [2023-12-16 05:53:32,548 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2023-12-16 05:53:32,548 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 18 states have (on average 1.5555555555555556) internal successors, (28), 16 states have internal predecessors, (28), 7 states have call successors, (8), 8 states have call predecessors, (8), 3 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) Word has length 39 [2023-12-16 05:53:32,548 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-16 05:53:32,549 INFO L225 Difference]: With dead ends: 177 [2023-12-16 05:53:32,549 INFO L226 Difference]: Without dead ends: 173 [2023-12-16 05:53:32,550 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 23 SyntacticMatches, 2 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 388 ImplicationChecksByTransitivity, 7.8s TimeCoverageRelationStatistics Valid=180, Invalid=1887, Unknown=3, NotChecked=0, Total=2070 [2023-12-16 05:53:32,551 INFO L413 NwaCegarLoop]: 38 mSDtfsCounter, 122 mSDsluCounter, 371 mSDsCounter, 0 mSdLazyCounter, 1384 mSolverCounterSat, 33 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 129 SdHoareTripleChecker+Valid, 409 SdHoareTripleChecker+Invalid, 1418 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 33 IncrementalHoareTripleChecker+Valid, 1384 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.2s IncrementalHoareTripleChecker+Time [2023-12-16 05:53:32,551 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [129 Valid, 409 Invalid, 1418 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [33 Valid, 1384 Invalid, 1 Unknown, 0 Unchecked, 5.2s Time] [2023-12-16 05:53:32,551 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 173 states. [2023-12-16 05:53:32,573 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 173 to 168. [2023-12-16 05:53:32,573 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 168 states, 104 states have (on average 1.1153846153846154) internal successors, (116), 115 states have internal predecessors, (116), 38 states have call successors, (38), 20 states have call predecessors, (38), 25 states have return successors, (51), 36 states have call predecessors, (51), 37 states have call successors, (51) [2023-12-16 05:53:32,574 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 168 states to 168 states and 205 transitions. [2023-12-16 05:53:32,574 INFO L78 Accepts]: Start accepts. Automaton has 168 states and 205 transitions. Word has length 39 [2023-12-16 05:53:32,574 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-16 05:53:32,574 INFO L495 AbstractCegarLoop]: Abstraction has 168 states and 205 transitions. [2023-12-16 05:53:32,574 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 18 states have (on average 1.5555555555555556) internal successors, (28), 16 states have internal predecessors, (28), 7 states have call successors, (8), 8 states have call predecessors, (8), 3 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) [2023-12-16 05:53:32,574 INFO L276 IsEmpty]: Start isEmpty. Operand 168 states and 205 transitions. [2023-12-16 05:53:32,575 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2023-12-16 05:53:32,575 INFO L187 NwaCegarLoop]: Found error trace [2023-12-16 05:53:32,575 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-16 05:53:32,598 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-12-16 05:53:32,780 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-16 05:53:32,780 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-16 05:53:32,781 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-16 05:53:32,781 INFO L85 PathProgramCache]: Analyzing trace with hash -603691064, now seen corresponding path program 1 times [2023-12-16 05:53:32,781 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-16 05:53:32,781 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [261791919] [2023-12-16 05:53:32,781 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-16 05:53:32,781 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-16 05:53:32,804 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-16 05:53:32,804 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [548244065] [2023-12-16 05:53:32,804 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-16 05:53:32,804 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-16 05:53:32,804 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-16 05:53:32,822 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) [2023-12-16 05:53:32,823 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-12-16 05:53:33,047 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-16 05:53:33,050 INFO L262 TraceCheckSpWp]: Trace formula consists of 564 conjuncts, 133 conjunts are in the unsatisfiable core [2023-12-16 05:53:33,053 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-16 05:53:33,098 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-16 05:53:33,102 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 15 [2023-12-16 05:53:33,104 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-16 05:53:33,168 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-16 05:53:33,172 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-16 05:53:33,655 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-16 05:53:33,656 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2023-12-16 05:53:33,660 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2023-12-16 05:53:33,708 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-12-16 05:53:33,708 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-16 05:53:33,841 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-16 05:53:33,841 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [261791919] [2023-12-16 05:53:33,841 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-16 05:53:33,841 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [548244065] [2023-12-16 05:53:33,841 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [548244065] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-16 05:53:33,841 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-16 05:53:33,841 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22] total 22 [2023-12-16 05:53:33,841 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1147221713] [2023-12-16 05:53:33,841 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-16 05:53:33,842 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2023-12-16 05:53:33,842 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-16 05:53:33,843 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2023-12-16 05:53:33,843 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=584, Unknown=0, NotChecked=0, Total=650 [2023-12-16 05:53:33,843 INFO L87 Difference]: Start difference. First operand 168 states and 205 transitions. Second operand has 22 states, 18 states have (on average 1.5555555555555556) internal successors, (28), 17 states have internal predecessors, (28), 7 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2023-12-16 05:53:34,695 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-16 05:53:34,695 INFO L93 Difference]: Finished difference Result 177 states and 212 transitions. [2023-12-16 05:53:34,695 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2023-12-16 05:53:34,696 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 18 states have (on average 1.5555555555555556) internal successors, (28), 17 states have internal predecessors, (28), 7 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Word has length 40 [2023-12-16 05:53:34,696 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-16 05:53:34,699 INFO L225 Difference]: With dead ends: 177 [2023-12-16 05:53:34,699 INFO L226 Difference]: Without dead ends: 175 [2023-12-16 05:53:34,700 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 18 SyntacticMatches, 3 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 251 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=141, Invalid=1265, Unknown=0, NotChecked=0, Total=1406 [2023-12-16 05:53:34,700 INFO L413 NwaCegarLoop]: 32 mSDtfsCounter, 41 mSDsluCounter, 432 mSDsCounter, 0 mSdLazyCounter, 627 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 42 SdHoareTripleChecker+Valid, 464 SdHoareTripleChecker+Invalid, 649 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 627 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-12-16 05:53:34,700 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [42 Valid, 464 Invalid, 649 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 627 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-12-16 05:53:34,701 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 175 states. [2023-12-16 05:53:34,736 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 175 to 172. [2023-12-16 05:53:34,736 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 172 states, 107 states have (on average 1.1121495327102804) internal successors, (119), 118 states have internal predecessors, (119), 38 states have call successors, (38), 21 states have call predecessors, (38), 26 states have return successors, (51), 36 states have call predecessors, (51), 37 states have call successors, (51) [2023-12-16 05:53:34,753 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 172 states to 172 states and 208 transitions. [2023-12-16 05:53:34,753 INFO L78 Accepts]: Start accepts. Automaton has 172 states and 208 transitions. Word has length 40 [2023-12-16 05:53:34,753 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-16 05:53:34,753 INFO L495 AbstractCegarLoop]: Abstraction has 172 states and 208 transitions. [2023-12-16 05:53:34,753 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 18 states have (on average 1.5555555555555556) internal successors, (28), 17 states have internal predecessors, (28), 7 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2023-12-16 05:53:34,753 INFO L276 IsEmpty]: Start isEmpty. Operand 172 states and 208 transitions. [2023-12-16 05:53:34,754 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2023-12-16 05:53:34,754 INFO L187 NwaCegarLoop]: Found error trace [2023-12-16 05:53:34,754 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-16 05:53:34,768 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2023-12-16 05:53:34,961 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-16 05:53:34,961 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-16 05:53:34,961 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-16 05:53:34,961 INFO L85 PathProgramCache]: Analyzing trace with hash -1785388392, now seen corresponding path program 1 times [2023-12-16 05:53:34,961 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-16 05:53:34,962 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [343635880] [2023-12-16 05:53:34,962 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-16 05:53:34,962 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-16 05:53:34,998 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-16 05:53:34,999 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [460114097] [2023-12-16 05:53:34,999 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-16 05:53:34,999 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-16 05:53:34,999 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-16 05:53:35,013 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-16 05:53:35,028 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-12-16 05:53:35,318 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-16 05:53:35,324 INFO L262 TraceCheckSpWp]: Trace formula consists of 796 conjuncts, 217 conjunts are in the unsatisfiable core [2023-12-16 05:53:35,329 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-16 05:53:35,337 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-16 05:53:35,434 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-16 05:53:35,439 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-16 05:53:35,448 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-16 05:53:35,462 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-16 05:53:35,652 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-16 05:53:35,655 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 15 [2023-12-16 05:53:35,661 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-16 05:53:35,725 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-16 05:53:35,857 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-16 05:53:35,861 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 19 [2023-12-16 05:53:35,864 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-16 05:53:35,868 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-16 05:53:36,312 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-16 05:53:36,316 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 10 [2023-12-16 05:53:36,362 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 1 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-16 05:53:36,363 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-16 05:53:36,460 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-16 05:53:36,460 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [343635880] [2023-12-16 05:53:36,461 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-16 05:53:36,461 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [460114097] [2023-12-16 05:53:36,461 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [460114097] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-16 05:53:36,461 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-16 05:53:36,461 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22] total 22 [2023-12-16 05:53:36,461 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1495803331] [2023-12-16 05:53:36,461 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-16 05:53:36,461 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2023-12-16 05:53:36,461 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-16 05:53:36,462 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2023-12-16 05:53:36,462 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=73, Invalid=577, Unknown=0, NotChecked=0, Total=650 [2023-12-16 05:53:36,462 INFO L87 Difference]: Start difference. First operand 172 states and 208 transitions. Second operand has 22 states, 19 states have (on average 1.6842105263157894) internal successors, (32), 16 states have internal predecessors, (32), 8 states have call successors, (9), 9 states have call predecessors, (9), 4 states have return successors, (4), 3 states have call predecessors, (4), 4 states have call successors, (4) [2023-12-16 05:53:40,487 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-16 05:53:42,043 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-16 05:53:42,043 INFO L93 Difference]: Finished difference Result 223 states and 264 transitions. [2023-12-16 05:53:42,044 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2023-12-16 05:53:42,044 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 19 states have (on average 1.6842105263157894) internal successors, (32), 16 states have internal predecessors, (32), 8 states have call successors, (9), 9 states have call predecessors, (9), 4 states have return successors, (4), 3 states have call predecessors, (4), 4 states have call successors, (4) Word has length 45 [2023-12-16 05:53:42,045 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-16 05:53:42,046 INFO L225 Difference]: With dead ends: 223 [2023-12-16 05:53:42,046 INFO L226 Difference]: Without dead ends: 219 [2023-12-16 05:53:42,046 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 64 GetRequests, 23 SyntacticMatches, 3 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 245 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=162, Invalid=1398, Unknown=0, NotChecked=0, Total=1560 [2023-12-16 05:53:42,047 INFO L413 NwaCegarLoop]: 44 mSDtfsCounter, 127 mSDsluCounter, 403 mSDsCounter, 0 mSdLazyCounter, 1076 mSolverCounterSat, 34 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 134 SdHoareTripleChecker+Valid, 447 SdHoareTripleChecker+Invalid, 1111 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 1076 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.0s IncrementalHoareTripleChecker+Time [2023-12-16 05:53:42,047 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [134 Valid, 447 Invalid, 1111 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 1076 Invalid, 1 Unknown, 0 Unchecked, 5.0s Time] [2023-12-16 05:53:42,047 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 219 states. [2023-12-16 05:53:42,077 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 219 to 212. [2023-12-16 05:53:42,077 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 212 states, 133 states have (on average 1.112781954887218) internal successors, (148), 146 states have internal predecessors, (148), 46 states have call successors, (46), 27 states have call predecessors, (46), 32 states have return successors, (61), 43 states have call predecessors, (61), 45 states have call successors, (61) [2023-12-16 05:53:42,080 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 212 states to 212 states and 255 transitions. [2023-12-16 05:53:42,080 INFO L78 Accepts]: Start accepts. Automaton has 212 states and 255 transitions. Word has length 45 [2023-12-16 05:53:42,080 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-16 05:53:42,080 INFO L495 AbstractCegarLoop]: Abstraction has 212 states and 255 transitions. [2023-12-16 05:53:42,080 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 19 states have (on average 1.6842105263157894) internal successors, (32), 16 states have internal predecessors, (32), 8 states have call successors, (9), 9 states have call predecessors, (9), 4 states have return successors, (4), 3 states have call predecessors, (4), 4 states have call successors, (4) [2023-12-16 05:53:42,080 INFO L276 IsEmpty]: Start isEmpty. Operand 212 states and 255 transitions. [2023-12-16 05:53:42,081 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2023-12-16 05:53:42,081 INFO L187 NwaCegarLoop]: Found error trace [2023-12-16 05:53:42,081 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-16 05:53:42,088 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2023-12-16 05:53:42,289 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2023-12-16 05:53:42,289 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-16 05:53:42,289 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-16 05:53:42,289 INFO L85 PathProgramCache]: Analyzing trace with hash 1730585129, now seen corresponding path program 1 times [2023-12-16 05:53:42,289 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-16 05:53:42,289 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1188010890] [2023-12-16 05:53:42,289 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-16 05:53:42,290 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-16 05:53:42,326 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-16 05:53:42,327 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1490240137] [2023-12-16 05:53:42,327 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-16 05:53:42,327 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-16 05:53:42,327 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-16 05:53:42,333 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-16 05:53:42,358 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-12-16 05:53:42,528 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-16 05:53:42,530 INFO L262 TraceCheckSpWp]: Trace formula consists of 579 conjuncts, 85 conjunts are in the unsatisfiable core [2023-12-16 05:53:42,533 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-16 05:53:42,563 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 15 [2023-12-16 05:53:42,565 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-16 05:53:42,634 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-16 05:53:42,640 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-16 05:53:43,062 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 14 [2023-12-16 05:53:43,065 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2023-12-16 05:53:43,113 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 9 proven. 6 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2023-12-16 05:53:43,113 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-16 05:53:43,275 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2023-12-16 05:53:43,275 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-16 05:53:43,275 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1188010890] [2023-12-16 05:53:43,275 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-16 05:53:43,275 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1490240137] [2023-12-16 05:53:43,275 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1490240137] provided 1 perfect and 1 imperfect interpolant sequences [2023-12-16 05:53:43,275 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-12-16 05:53:43,275 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [21] total 27 [2023-12-16 05:53:43,275 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [326848349] [2023-12-16 05:53:43,275 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-16 05:53:43,275 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-12-16 05:53:43,276 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-16 05:53:43,276 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-12-16 05:53:43,276 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=635, Unknown=0, NotChecked=0, Total=702 [2023-12-16 05:53:43,276 INFO L87 Difference]: Start difference. First operand 212 states and 255 transitions. Second operand has 8 states, 6 states have (on average 3.8333333333333335) internal successors, (23), 6 states have internal predecessors, (23), 4 states have call successors, (9), 3 states have call predecessors, (9), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2023-12-16 05:53:43,462 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-16 05:53:43,463 INFO L93 Difference]: Finished difference Result 246 states and 298 transitions. [2023-12-16 05:53:43,463 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-12-16 05:53:43,463 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 3.8333333333333335) internal successors, (23), 6 states have internal predecessors, (23), 4 states have call successors, (9), 3 states have call predecessors, (9), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 46 [2023-12-16 05:53:43,463 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-16 05:53:43,464 INFO L225 Difference]: With dead ends: 246 [2023-12-16 05:53:43,464 INFO L226 Difference]: Without dead ends: 244 [2023-12-16 05:53:43,465 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 93 GetRequests, 60 SyntacticMatches, 5 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 163 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=81, Invalid=789, Unknown=0, NotChecked=0, Total=870 [2023-12-16 05:53:43,465 INFO L413 NwaCegarLoop]: 48 mSDtfsCounter, 17 mSDsluCounter, 229 mSDsCounter, 0 mSdLazyCounter, 113 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 277 SdHoareTripleChecker+Invalid, 124 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 113 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-16 05:53:43,466 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 277 Invalid, 124 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 113 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-16 05:53:43,466 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 244 states. [2023-12-16 05:53:43,512 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 244 to 220. [2023-12-16 05:53:43,513 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 220 states, 139 states have (on average 1.1007194244604317) internal successors, (153), 152 states have internal predecessors, (153), 46 states have call successors, (46), 29 states have call predecessors, (46), 34 states have return successors, (61), 43 states have call predecessors, (61), 45 states have call successors, (61) [2023-12-16 05:53:43,514 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 220 states to 220 states and 260 transitions. [2023-12-16 05:53:43,514 INFO L78 Accepts]: Start accepts. Automaton has 220 states and 260 transitions. Word has length 46 [2023-12-16 05:53:43,515 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-16 05:53:43,515 INFO L495 AbstractCegarLoop]: Abstraction has 220 states and 260 transitions. [2023-12-16 05:53:43,515 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 3.8333333333333335) internal successors, (23), 6 states have internal predecessors, (23), 4 states have call successors, (9), 3 states have call predecessors, (9), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2023-12-16 05:53:43,515 INFO L276 IsEmpty]: Start isEmpty. Operand 220 states and 260 transitions. [2023-12-16 05:53:43,515 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2023-12-16 05:53:43,515 INFO L187 NwaCegarLoop]: Found error trace [2023-12-16 05:53:43,515 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-16 05:53:43,522 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2023-12-16 05:53:43,721 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-16 05:53:43,722 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-16 05:53:43,722 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-16 05:53:43,722 INFO L85 PathProgramCache]: Analyzing trace with hash 1711293408, now seen corresponding path program 2 times [2023-12-16 05:53:43,722 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-16 05:53:43,722 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1427456575] [2023-12-16 05:53:43,722 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-16 05:53:43,722 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-16 05:53:43,747 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-16 05:53:43,748 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [562541957] [2023-12-16 05:53:43,748 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-12-16 05:53:43,748 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-16 05:53:43,748 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-16 05:53:43,749 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-16 05:53:43,757 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2023-12-16 05:53:44,026 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-12-16 05:53:44,027 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-16 05:53:44,031 INFO L262 TraceCheckSpWp]: Trace formula consists of 1026 conjuncts, 132 conjunts are in the unsatisfiable core [2023-12-16 05:53:44,034 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-16 05:53:44,053 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-16 05:53:44,055 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-16 05:53:44,070 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-16 05:53:44,084 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-16 05:53:44,198 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 40 treesize of output 28 [2023-12-16 05:53:44,216 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 24 [2023-12-16 05:53:44,219 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 40 treesize of output 17 [2023-12-16 05:53:44,272 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-16 05:53:44,292 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-16 05:53:44,367 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 19 [2023-12-16 05:53:44,372 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 40 treesize of output 28 [2023-12-16 05:53:44,374 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 40 treesize of output 17 [2023-12-16 05:53:44,428 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-16 05:53:44,430 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 25 treesize of output 17 [2023-12-16 05:53:44,525 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 13 [2023-12-16 05:53:44,527 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 9 [2023-12-16 05:53:44,543 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 7 proven. 18 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-12-16 05:53:44,543 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-16 05:53:44,894 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 10 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-12-16 05:53:44,894 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-16 05:53:44,894 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1427456575] [2023-12-16 05:53:44,894 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-16 05:53:44,894 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [562541957] [2023-12-16 05:53:44,894 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [562541957] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-16 05:53:44,894 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-16 05:53:44,894 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 14] total 33 [2023-12-16 05:53:44,895 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1849275833] [2023-12-16 05:53:44,895 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-16 05:53:44,895 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2023-12-16 05:53:44,895 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-16 05:53:44,895 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2023-12-16 05:53:44,896 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=105, Invalid=951, Unknown=0, NotChecked=0, Total=1056 [2023-12-16 05:53:44,896 INFO L87 Difference]: Start difference. First operand 220 states and 260 transitions. Second operand has 33 states, 31 states have (on average 1.8709677419354838) internal successors, (58), 25 states have internal predecessors, (58), 12 states have call successors, (18), 12 states have call predecessors, (18), 5 states have return successors, (8), 6 states have call predecessors, (8), 5 states have call successors, (8) [2023-12-16 05:53:49,149 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-12-16 05:53:50,380 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-16 05:53:50,380 INFO L93 Difference]: Finished difference Result 401 states and 498 transitions. [2023-12-16 05:53:50,381 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2023-12-16 05:53:50,381 INFO L78 Accepts]: Start accepts. Automaton has has 33 states, 31 states have (on average 1.8709677419354838) internal successors, (58), 25 states have internal predecessors, (58), 12 states have call successors, (18), 12 states have call predecessors, (18), 5 states have return successors, (8), 6 states have call predecessors, (8), 5 states have call successors, (8) Word has length 50 [2023-12-16 05:53:50,381 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-16 05:53:50,382 INFO L225 Difference]: With dead ends: 401 [2023-12-16 05:53:50,382 INFO L226 Difference]: Without dead ends: 345 [2023-12-16 05:53:50,383 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 119 GetRequests, 69 SyntacticMatches, 1 SemanticMatches, 49 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 582 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=277, Invalid=2273, Unknown=0, NotChecked=0, Total=2550 [2023-12-16 05:53:50,384 INFO L413 NwaCegarLoop]: 19 mSDtfsCounter, 93 mSDsluCounter, 198 mSDsCounter, 0 mSdLazyCounter, 1510 mSolverCounterSat, 56 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 106 SdHoareTripleChecker+Valid, 217 SdHoareTripleChecker+Invalid, 1567 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 56 IncrementalHoareTripleChecker+Valid, 1510 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.0s IncrementalHoareTripleChecker+Time [2023-12-16 05:53:50,384 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [106 Valid, 217 Invalid, 1567 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [56 Valid, 1510 Invalid, 1 Unknown, 0 Unchecked, 5.0s Time] [2023-12-16 05:53:50,384 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 345 states. [2023-12-16 05:53:50,454 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 345 to 297. [2023-12-16 05:53:50,455 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 297 states, 188 states have (on average 1.101063829787234) internal successors, (207), 204 states have internal predecessors, (207), 62 states have call successors, (62), 39 states have call predecessors, (62), 46 states have return successors, (92), 60 states have call predecessors, (92), 61 states have call successors, (92) [2023-12-16 05:53:50,456 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 297 states to 297 states and 361 transitions. [2023-12-16 05:53:50,456 INFO L78 Accepts]: Start accepts. Automaton has 297 states and 361 transitions. Word has length 50 [2023-12-16 05:53:50,464 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-16 05:53:50,465 INFO L495 AbstractCegarLoop]: Abstraction has 297 states and 361 transitions. [2023-12-16 05:53:50,465 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 33 states, 31 states have (on average 1.8709677419354838) internal successors, (58), 25 states have internal predecessors, (58), 12 states have call successors, (18), 12 states have call predecessors, (18), 5 states have return successors, (8), 6 states have call predecessors, (8), 5 states have call successors, (8) [2023-12-16 05:53:50,465 INFO L276 IsEmpty]: Start isEmpty. Operand 297 states and 361 transitions. [2023-12-16 05:53:50,465 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2023-12-16 05:53:50,465 INFO L187 NwaCegarLoop]: Found error trace [2023-12-16 05:53:50,465 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-16 05:53:50,490 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2023-12-16 05:53:50,672 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2023-12-16 05:53:50,672 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-16 05:53:50,673 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-16 05:53:50,673 INFO L85 PathProgramCache]: Analyzing trace with hash -213043205, now seen corresponding path program 1 times [2023-12-16 05:53:50,673 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-16 05:53:50,673 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [64085031] [2023-12-16 05:53:50,673 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-16 05:53:50,673 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-16 05:53:50,704 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-16 05:53:50,704 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1401707497] [2023-12-16 05:53:50,704 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-16 05:53:50,705 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-16 05:53:50,705 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-16 05:53:50,705 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-16 05:53:50,707 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2023-12-16 05:53:50,973 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-16 05:53:50,977 INFO L262 TraceCheckSpWp]: Trace formula consists of 813 conjuncts, 91 conjunts are in the unsatisfiable core [2023-12-16 05:53:50,979 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-16 05:53:50,984 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-16 05:53:51,001 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-16 05:53:51,006 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-16 05:53:51,254 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-16 05:53:51,256 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2023-12-16 05:53:51,290 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 7 proven. 4 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2023-12-16 05:53:51,290 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-16 05:53:51,467 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2023-12-16 05:53:51,467 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-16 05:53:51,467 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [64085031] [2023-12-16 05:53:51,467 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-16 05:53:51,467 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1401707497] [2023-12-16 05:53:51,467 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1401707497] provided 1 perfect and 1 imperfect interpolant sequences [2023-12-16 05:53:51,467 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-12-16 05:53:51,467 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [13] total 20 [2023-12-16 05:53:51,468 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2032236228] [2023-12-16 05:53:51,468 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-16 05:53:51,468 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-12-16 05:53:51,468 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-16 05:53:51,468 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-12-16 05:53:51,468 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=52, Invalid=328, Unknown=0, NotChecked=0, Total=380 [2023-12-16 05:53:51,468 INFO L87 Difference]: Start difference. First operand 297 states and 361 transitions. Second operand has 10 states, 8 states have (on average 3.5) internal successors, (28), 7 states have internal predecessors, (28), 5 states have call successors, (10), 4 states have call predecessors, (10), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2023-12-16 05:53:51,738 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-16 05:53:51,738 INFO L93 Difference]: Finished difference Result 370 states and 451 transitions. [2023-12-16 05:53:51,738 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2023-12-16 05:53:51,739 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 3.5) internal successors, (28), 7 states have internal predecessors, (28), 5 states have call successors, (10), 4 states have call predecessors, (10), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 51 [2023-12-16 05:53:51,739 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-16 05:53:51,740 INFO L225 Difference]: With dead ends: 370 [2023-12-16 05:53:51,740 INFO L226 Difference]: Without dead ends: 368 [2023-12-16 05:53:51,741 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 105 GetRequests, 79 SyntacticMatches, 4 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 74 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=70, Invalid=482, Unknown=0, NotChecked=0, Total=552 [2023-12-16 05:53:51,741 INFO L413 NwaCegarLoop]: 46 mSDtfsCounter, 26 mSDsluCounter, 298 mSDsCounter, 0 mSdLazyCounter, 195 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 344 SdHoareTripleChecker+Invalid, 209 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 195 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-12-16 05:53:51,741 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [26 Valid, 344 Invalid, 209 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 195 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-12-16 05:53:51,742 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 368 states. [2023-12-16 05:53:51,797 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 368 to 364. [2023-12-16 05:53:51,797 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 364 states, 229 states have (on average 1.1048034934497817) internal successors, (253), 251 states have internal predecessors, (253), 80 states have call successors, (80), 47 states have call predecessors, (80), 54 states have return successors, (110), 75 states have call predecessors, (110), 79 states have call successors, (110) [2023-12-16 05:53:51,800 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 364 states to 364 states and 443 transitions. [2023-12-16 05:53:51,800 INFO L78 Accepts]: Start accepts. Automaton has 364 states and 443 transitions. Word has length 51 [2023-12-16 05:53:51,800 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-16 05:53:51,801 INFO L495 AbstractCegarLoop]: Abstraction has 364 states and 443 transitions. [2023-12-16 05:53:51,801 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 3.5) internal successors, (28), 7 states have internal predecessors, (28), 5 states have call successors, (10), 4 states have call predecessors, (10), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2023-12-16 05:53:51,801 INFO L276 IsEmpty]: Start isEmpty. Operand 364 states and 443 transitions. [2023-12-16 05:53:51,801 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2023-12-16 05:53:51,801 INFO L187 NwaCegarLoop]: Found error trace [2023-12-16 05:53:51,801 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-16 05:53:51,810 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2023-12-16 05:53:52,008 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2023-12-16 05:53:52,008 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-16 05:53:52,009 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-16 05:53:52,009 INFO L85 PathProgramCache]: Analyzing trace with hash -300465721, now seen corresponding path program 1 times [2023-12-16 05:53:52,009 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-16 05:53:52,009 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1536225106] [2023-12-16 05:53:52,009 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-16 05:53:52,009 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-16 05:53:52,030 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-16 05:53:52,030 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1657055651] [2023-12-16 05:53:52,030 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-16 05:53:52,030 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-16 05:53:52,031 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-16 05:53:52,031 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-16 05:53:52,053 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2023-12-16 05:53:52,289 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-16 05:53:52,292 INFO L262 TraceCheckSpWp]: Trace formula consists of 881 conjuncts, 90 conjunts are in the unsatisfiable core [2023-12-16 05:53:52,296 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-16 05:53:52,305 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-16 05:53:52,308 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-16 05:53:52,340 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-16 05:53:52,343 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-16 05:53:52,375 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-16 05:53:52,391 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-16 05:53:52,540 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 44 treesize of output 32 [2023-12-16 05:53:52,565 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 46 treesize of output 23 [2023-12-16 05:53:52,609 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 13 [2023-12-16 05:53:52,611 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 9 [2023-12-16 05:53:52,624 INFO L134 CoverageAnalysis]: Checked inductivity of 87 backedges. 50 proven. 1 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2023-12-16 05:53:52,625 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-16 05:53:52,999 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-16 05:53:53,000 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1536225106] [2023-12-16 05:53:53,000 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-16 05:53:53,000 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1657055651] [2023-12-16 05:53:53,000 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1657055651] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-16 05:53:53,000 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-16 05:53:53,000 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2023-12-16 05:53:53,000 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1145820] [2023-12-16 05:53:53,000 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-16 05:53:53,000 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2023-12-16 05:53:53,000 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-16 05:53:53,010 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2023-12-16 05:53:53,011 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=70, Invalid=530, Unknown=0, NotChecked=0, Total=600 [2023-12-16 05:53:53,011 INFO L87 Difference]: Start difference. First operand 364 states and 443 transitions. Second operand has 17 states, 15 states have (on average 2.4) internal successors, (36), 12 states have internal predecessors, (36), 6 states have call successors, (14), 6 states have call predecessors, (14), 3 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) [2023-12-16 05:53:53,531 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-16 05:53:53,531 INFO L93 Difference]: Finished difference Result 672 states and 850 transitions. [2023-12-16 05:53:53,531 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2023-12-16 05:53:53,531 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 15 states have (on average 2.4) internal successors, (36), 12 states have internal predecessors, (36), 6 states have call successors, (14), 6 states have call predecessors, (14), 3 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) Word has length 75 [2023-12-16 05:53:53,532 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-16 05:53:53,534 INFO L225 Difference]: With dead ends: 672 [2023-12-16 05:53:53,534 INFO L226 Difference]: Without dead ends: 420 [2023-12-16 05:53:53,537 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 120 GetRequests, 81 SyntacticMatches, 0 SemanticMatches, 39 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 303 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=193, Invalid=1447, Unknown=0, NotChecked=0, Total=1640 [2023-12-16 05:53:53,541 INFO L413 NwaCegarLoop]: 27 mSDtfsCounter, 57 mSDsluCounter, 193 mSDsCounter, 0 mSdLazyCounter, 474 mSolverCounterSat, 43 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 58 SdHoareTripleChecker+Valid, 220 SdHoareTripleChecker+Invalid, 517 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 43 IncrementalHoareTripleChecker+Valid, 474 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-12-16 05:53:53,541 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [58 Valid, 220 Invalid, 517 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [43 Valid, 474 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-12-16 05:53:53,542 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 420 states. [2023-12-16 05:53:53,632 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 420 to 412. [2023-12-16 05:53:53,633 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 412 states, 259 states have (on average 1.0926640926640927) internal successors, (283), 281 states have internal predecessors, (283), 84 states have call successors, (84), 51 states have call predecessors, (84), 68 states have return successors, (134), 79 states have call predecessors, (134), 83 states have call successors, (134) [2023-12-16 05:53:53,634 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 412 states to 412 states and 501 transitions. [2023-12-16 05:53:53,635 INFO L78 Accepts]: Start accepts. Automaton has 412 states and 501 transitions. Word has length 75 [2023-12-16 05:53:53,635 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-16 05:53:53,635 INFO L495 AbstractCegarLoop]: Abstraction has 412 states and 501 transitions. [2023-12-16 05:53:53,635 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 15 states have (on average 2.4) internal successors, (36), 12 states have internal predecessors, (36), 6 states have call successors, (14), 6 states have call predecessors, (14), 3 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) [2023-12-16 05:53:53,635 INFO L276 IsEmpty]: Start isEmpty. Operand 412 states and 501 transitions. [2023-12-16 05:53:53,636 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2023-12-16 05:53:53,636 INFO L187 NwaCegarLoop]: Found error trace [2023-12-16 05:53:53,636 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-16 05:53:53,645 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2023-12-16 05:53:53,836 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2023-12-16 05:53:53,836 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-16 05:53:53,837 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-16 05:53:53,837 INFO L85 PathProgramCache]: Analyzing trace with hash 861698770, now seen corresponding path program 1 times [2023-12-16 05:53:53,837 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-16 05:53:53,837 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1484995930] [2023-12-16 05:53:53,837 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-16 05:53:53,837 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-16 05:53:53,869 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-16 05:53:53,870 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1865516289] [2023-12-16 05:53:53,870 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-16 05:53:53,870 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-16 05:53:53,870 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-16 05:53:53,890 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-16 05:53:53,943 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2023-12-16 05:53:54,249 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-16 05:53:54,254 INFO L262 TraceCheckSpWp]: Trace formula consists of 852 conjuncts, 317 conjunts are in the unsatisfiable core [2023-12-16 05:53:54,261 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-16 05:53:54,272 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-16 05:53:54,276 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2023-12-16 05:53:54,390 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-16 05:53:54,395 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-16 05:53:54,405 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-16 05:53:54,412 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-16 05:53:54,423 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-16 05:53:54,438 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-16 05:53:54,491 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-16 05:53:54,500 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-16 05:53:54,769 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-16 05:53:54,815 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-16 05:53:54,946 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-16 05:53:55,080 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-16 05:53:55,103 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-12-16 05:53:55,165 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-12-16 05:54:03,770 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 50 treesize of output 38 [2023-12-16 05:54:07,930 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-16 05:54:07,930 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 38 treesize of output 38 [2023-12-16 05:54:12,212 INFO L349 Elim1Store]: treesize reduction 22, result has 56.0 percent of original size [2023-12-16 05:54:12,212 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 72 treesize of output 73 [2023-12-16 05:54:12,332 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2023-12-16 05:54:12,686 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-16 05:54:12,687 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 103 treesize of output 111 Received shutdown request... [2023-12-16 05:54:18,502 WARN L340 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Timeout while monitored process is still running, waiting 1000 ms for graceful end [2023-12-16 05:54:18,510 WARN L340 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Timeout while monitored process is still running, waiting 1000 ms for graceful end [2023-12-16 05:54:19,523 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2023-12-16 05:54:19,723 WARN L435 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Forcibly destroying the process [2023-12-16 05:54:19,741 INFO L805 garLoopResultBuilder]: Registering result TIMEOUT for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2023-12-16 05:54:19,741 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12 [2023-12-16 05:54:19,741 WARN L619 AbstractCegarLoop]: Verification canceled: while NwaCegarLoop was analyzing trace of length 75 with TraceHistMax 5,while TraceCheckSpWp was constructing forward predicates,while executing Executor. [2023-12-16 05:54:19,744 INFO L445 BasicCegarLoop]: Path program histogram: [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-16 05:54:19,746 INFO L179 ceAbstractionStarter]: Computing trace abstraction results [2023-12-16 05:54:19,747 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 16.12 05:54:19 BoogieIcfgContainer [2023-12-16 05:54:19,747 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2023-12-16 05:54:19,747 INFO L158 Benchmark]: Toolchain (without parser) took 73919.40ms. Allocated memory was 268.4MB in the beginning and 326.1MB in the end (delta: 57.7MB). Free memory was 217.2MB in the beginning and 149.9MB in the end (delta: 67.3MB). Peak memory consumption was 125.7MB. Max. memory is 8.0GB. [2023-12-16 05:54:19,747 INFO L158 Benchmark]: CDTParser took 0.09ms. Allocated memory is still 179.3MB. Free memory is still 127.9MB. There was no memory consumed. Max. memory is 8.0GB. [2023-12-16 05:54:19,748 INFO L158 Benchmark]: CACSL2BoogieTranslator took 247.48ms. Allocated memory is still 268.4MB. Free memory was 217.2MB in the beginning and 204.5MB in the end (delta: 12.7MB). Peak memory consumption was 12.6MB. Max. memory is 8.0GB. [2023-12-16 05:54:19,748 INFO L158 Benchmark]: Boogie Procedure Inliner took 60.40ms. Allocated memory is still 268.4MB. Free memory was 204.5MB in the beginning and 203.0MB in the end (delta: 1.5MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2023-12-16 05:54:19,748 INFO L158 Benchmark]: Boogie Preprocessor took 82.97ms. Allocated memory is still 268.4MB. Free memory was 203.0MB in the beginning and 199.3MB in the end (delta: 3.7MB). Peak memory consumption was 4.2MB. Max. memory is 8.0GB. [2023-12-16 05:54:19,748 INFO L158 Benchmark]: RCFGBuilder took 606.47ms. Allocated memory is still 268.4MB. Free memory was 199.3MB in the beginning and 171.0MB in the end (delta: 28.3MB). Peak memory consumption was 28.3MB. Max. memory is 8.0GB. [2023-12-16 05:54:19,748 INFO L158 Benchmark]: TraceAbstraction took 72915.42ms. Allocated memory was 268.4MB in the beginning and 326.1MB in the end (delta: 57.7MB). Free memory was 170.5MB in the beginning and 149.9MB in the end (delta: 20.6MB). Peak memory consumption was 79.6MB. Max. memory is 8.0GB. [2023-12-16 05:54:19,749 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.09ms. Allocated memory is still 179.3MB. Free memory is still 127.9MB. There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 247.48ms. Allocated memory is still 268.4MB. Free memory was 217.2MB in the beginning and 204.5MB in the end (delta: 12.7MB). Peak memory consumption was 12.6MB. Max. memory is 8.0GB. * Boogie Procedure Inliner took 60.40ms. Allocated memory is still 268.4MB. Free memory was 204.5MB in the beginning and 203.0MB in the end (delta: 1.5MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * Boogie Preprocessor took 82.97ms. Allocated memory is still 268.4MB. Free memory was 203.0MB in the beginning and 199.3MB in the end (delta: 3.7MB). Peak memory consumption was 4.2MB. Max. memory is 8.0GB. * RCFGBuilder took 606.47ms. Allocated memory is still 268.4MB. Free memory was 199.3MB in the beginning and 171.0MB in the end (delta: 28.3MB). Peak memory consumption was 28.3MB. Max. memory is 8.0GB. * TraceAbstraction took 72915.42ms. Allocated memory was 268.4MB in the beginning and 326.1MB in the end (delta: 57.7MB). Free memory was 170.5MB in the beginning and 149.9MB in the end (delta: 20.6MB). Peak memory consumption was 79.6MB. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - TimeoutResultAtElement [Line: 37]: Timeout (TraceAbstraction) Unable to prove that a call to reach_error is unreachable (line 37). Cancelled while NwaCegarLoop was analyzing trace of length 75 with TraceHistMax 5,while TraceCheckSpWp was constructing forward predicates,while executing Executor. - StatisticsResult: Ultimate Automizer benchmark data CFG has 6 procedures, 50 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 72.8s, OverallIterations: 13, TraceHistogramMax: 7, PathProgramHistogramMax: 2, EmptinessCheckTime: 0.0s, AutomataDifference: 25.3s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 4 mSolverCounterUnknown, 799 SdHoareTripleChecker+Valid, 21.7s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 759 mSDsluCounter, 3305 SdHoareTripleChecker+Invalid, 21.0s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 2894 mSDsCounter, 391 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 7435 IncrementalHoareTripleChecker+Invalid, 7830 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 391 mSolverCounterUnsat, 411 mSDtfsCounter, 7435 mSolverCounterSat, 0.1s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 871 GetRequests, 480 SyntacticMatches, 21 SemanticMatches, 370 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2562 ImplicationChecksByTransitivity, 13.6s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=412occurred in iteration=12, InterpolantAutomatonStates: 209, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.5s AutomataMinimizationTime, 12 MinimizatonAttempts, 101 StatesRemovedByMinimization, 9 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.4s SsaConstructionTime, 1.4s SatisfiabilityAnalysisTime, 15.4s InterpolantComputationTime, 515 NumberOfCodeBlocks, 515 NumberOfCodeBlocksAsserted, 14 NumberOfCheckSat, 693 ConstructedInterpolants, 76 QuantifiedInterpolants, 9198 SizeOfPredicates, 468 NumberOfNonLiveVariables, 7605 ConjunctsInSsa, 1436 ConjunctsInUnsatCore, 17 InterpolantComputations, 6 PerfectInterpolantSequences, 217/305 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Completed graceful shutdown [2023-12-16 05:54:19,763 WARN L435 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Forcibly destroying the process [2023-12-16 05:54:19,766 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Forceful destruction successful, exit code 137