./Ultimate.py --spec ../../../trunk/examples/svcomp/properties/unreach-call.prp --file ../../../trunk/examples/svcomp/recursified_nla-digbench/recursified_dijkstra-u.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version c4f91361 Calling Ultimate with: /root/.sdkman/candidates/java/current/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../../../trunk/examples/svcomp/recursified_nla-digbench/recursified_dijkstra-u.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 0464cc7a685168b5fc1a1b0dd8da6141b4b98c7c538345750bda8185cd005644 --- Real Ultimate output --- This is Ultimate 0.2.3-dev-c4f9136-m [2023-11-23 15:23:56,552 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-23 15:23:56,612 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2023-11-23 15:23:56,617 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-23 15:23:56,617 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-23 15:23:56,639 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-23 15:23:56,639 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-23 15:23:56,640 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-23 15:23:56,640 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2023-11-23 15:23:56,640 INFO L153 SettingsManager]: * Use memory slicer=true [2023-11-23 15:23:56,640 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-23 15:23:56,641 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-23 15:23:56,641 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2023-11-23 15:23:56,641 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2023-11-23 15:23:56,641 INFO L153 SettingsManager]: * Use SBE=true [2023-11-23 15:23:56,642 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-23 15:23:56,642 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-23 15:23:56,642 INFO L153 SettingsManager]: * sizeof long=4 [2023-11-23 15:23:56,642 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-23 15:23:56,643 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-11-23 15:23:56,643 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-23 15:23:56,645 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-23 15:23:56,646 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-23 15:23:56,646 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-23 15:23:56,649 INFO L153 SettingsManager]: * sizeof long double=12 [2023-11-23 15:23:56,649 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-23 15:23:56,649 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-23 15:23:56,649 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-23 15:23:56,649 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2023-11-23 15:23:56,649 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2023-11-23 15:23:56,649 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-23 15:23:56,650 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-23 15:23:56,650 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-23 15:23:56,650 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-23 15:23:56,650 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-23 15:23:56,650 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2023-11-23 15:23:56,650 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-23 15:23:56,651 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2023-11-23 15:23:56,651 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2023-11-23 15:23:56,651 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-23 15:23:56,651 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2023-11-23 15:23:56,652 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-23 15:23:56,652 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 0464cc7a685168b5fc1a1b0dd8da6141b4b98c7c538345750bda8185cd005644 [2023-11-23 15:23:56,817 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-23 15:23:56,830 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-23 15:23:56,832 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-23 15:23:56,833 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-23 15:23:56,833 INFO L274 PluginConnector]: CDTParser initialized [2023-11-23 15:23:56,834 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/recursified_nla-digbench/recursified_dijkstra-u.c [2023-11-23 15:23:57,932 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-23 15:23:58,097 INFO L384 CDTParser]: Found 1 translation units. [2023-11-23 15:23:58,097 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/recursified_nla-digbench/recursified_dijkstra-u.c [2023-11-23 15:23:58,106 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/fc664d7f6/acdae3e4e88d425a9ae7db278711200f/FLAGa713bb8cc [2023-11-23 15:23:58,115 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/fc664d7f6/acdae3e4e88d425a9ae7db278711200f [2023-11-23 15:23:58,117 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-23 15:23:58,118 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-23 15:23:58,119 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-23 15:23:58,119 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-23 15:23:58,124 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-23 15:23:58,125 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.11 03:23:58" (1/1) ... [2023-11-23 15:23:58,125 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2e09da59 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 03:23:58, skipping insertion in model container [2023-11-23 15:23:58,125 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.11 03:23:58" (1/1) ... [2023-11-23 15:23:58,141 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-23 15:23:58,249 WARN L240 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_dijkstra-u.c[1076,1089] [2023-11-23 15:23:58,273 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-23 15:23:58,289 INFO L202 MainTranslator]: Completed pre-run [2023-11-23 15:23:58,297 WARN L240 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_dijkstra-u.c[1076,1089] [2023-11-23 15:23:58,315 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-23 15:23:58,325 INFO L206 MainTranslator]: Completed translation [2023-11-23 15:23:58,325 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 03:23:58 WrapperNode [2023-11-23 15:23:58,325 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-23 15:23:58,326 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-23 15:23:58,326 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-23 15:23:58,326 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-23 15:23:58,331 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 03:23:58" (1/1) ... [2023-11-23 15:23:58,339 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 03:23:58" (1/1) ... [2023-11-23 15:23:58,359 INFO L138 Inliner]: procedures = 17, calls = 173, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 114 [2023-11-23 15:23:58,360 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-23 15:23:58,360 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-23 15:23:58,360 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-23 15:23:58,361 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-23 15:23:58,368 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 03:23:58" (1/1) ... [2023-11-23 15:23:58,369 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 03:23:58" (1/1) ... [2023-11-23 15:23:58,385 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 03:23:58" (1/1) ... [2023-11-23 15:23:58,398 INFO L175 MemorySlicer]: Split 139 memory accesses to 6 slices as follows [2, 35, 30, 21, 29, 22]. 25 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2, 0, 0, 0, 0, 0]. The 11 writes are split as follows [0, 3, 2, 1, 3, 2]. [2023-11-23 15:23:58,399 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 03:23:58" (1/1) ... [2023-11-23 15:23:58,399 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 03:23:58" (1/1) ... [2023-11-23 15:23:58,405 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 03:23:58" (1/1) ... [2023-11-23 15:23:58,407 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 03:23:58" (1/1) ... [2023-11-23 15:23:58,408 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 03:23:58" (1/1) ... [2023-11-23 15:23:58,417 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 03:23:58" (1/1) ... [2023-11-23 15:23:58,421 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-23 15:23:58,421 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-23 15:23:58,421 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-23 15:23:58,421 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-23 15:23:58,422 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 03:23:58" (1/1) ... [2023-11-23 15:23:58,426 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-23 15:23:58,436 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 15:23:58,502 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-11-23 15:23:58,509 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-11-23 15:23:58,539 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-23 15:23:58,540 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_29_to_33_0 [2023-11-23 15:23:58,540 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_29_to_33_0 [2023-11-23 15:23:58,541 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2023-11-23 15:23:58,541 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2023-11-23 15:23:58,541 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2023-11-23 15:23:58,541 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2023-11-23 15:23:58,542 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#4 [2023-11-23 15:23:58,543 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#5 [2023-11-23 15:23:58,543 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2023-11-23 15:23:58,543 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2023-11-23 15:23:58,543 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2023-11-23 15:23:58,543 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2023-11-23 15:23:58,543 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2023-11-23 15:23:58,544 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#4 [2023-11-23 15:23:58,544 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#5 [2023-11-23 15:23:58,544 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_37_to_53_0 [2023-11-23 15:23:58,544 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_37_to_53_0 [2023-11-23 15:23:58,544 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-23 15:23:58,545 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-23 15:23:58,545 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2023-11-23 15:23:58,545 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2023-11-23 15:23:58,545 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2023-11-23 15:23:58,545 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2023-11-23 15:23:58,545 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#4 [2023-11-23 15:23:58,546 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#5 [2023-11-23 15:23:58,546 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-11-23 15:23:58,546 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-11-23 15:23:58,546 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2023-11-23 15:23:58,671 INFO L241 CfgBuilder]: Building ICFG [2023-11-23 15:23:58,679 INFO L267 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-23 15:23:58,965 INFO L282 CfgBuilder]: Performing block encoding [2023-11-23 15:23:58,985 INFO L304 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-23 15:23:58,990 INFO L309 CfgBuilder]: Removed 2 assume(true) statements. [2023-11-23 15:23:58,991 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.11 03:23:58 BoogieIcfgContainer [2023-11-23 15:23:58,991 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-23 15:23:58,993 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-23 15:23:58,993 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-23 15:23:58,995 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-23 15:23:58,995 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 23.11 03:23:58" (1/3) ... [2023-11-23 15:23:58,996 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4199a647 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.11 03:23:58, skipping insertion in model container [2023-11-23 15:23:58,996 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 03:23:58" (2/3) ... [2023-11-23 15:23:58,996 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4199a647 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.11 03:23:58, skipping insertion in model container [2023-11-23 15:23:58,996 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.11 03:23:58" (3/3) ... [2023-11-23 15:23:58,997 INFO L112 eAbstractionObserver]: Analyzing ICFG recursified_dijkstra-u.c [2023-11-23 15:23:59,009 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-23 15:23:59,010 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-11-23 15:23:59,041 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-23 15:23:59,046 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;@5605ef1a, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-23 15:23:59,046 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-11-23 15:23:59,049 INFO L276 IsEmpty]: Start isEmpty. Operand has 44 states, 26 states have (on average 1.3076923076923077) internal successors, (34), 29 states have internal predecessors, (34), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2023-11-23 15:23:59,054 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2023-11-23 15:23:59,054 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 15:23:59,055 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 15:23:59,055 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 15:23:59,059 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 15:23:59,059 INFO L85 PathProgramCache]: Analyzing trace with hash 1180092585, now seen corresponding path program 1 times [2023-11-23 15:23:59,065 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 15:23:59,065 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1947502215] [2023-11-23 15:23:59,065 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 15:23:59,066 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 15:23:59,143 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 15:23:59,195 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-23 15:23:59,197 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 15:23:59,201 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-23 15:23:59,202 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 15:23:59,202 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1947502215] [2023-11-23 15:23:59,202 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1947502215] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-23 15:23:59,202 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-23 15:23:59,203 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-11-23 15:23:59,204 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [37293567] [2023-11-23 15:23:59,204 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-23 15:23:59,207 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-23 15:23:59,207 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 15:23:59,232 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-23 15:23:59,233 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-23 15:23:59,234 INFO L87 Difference]: Start difference. First operand has 44 states, 26 states have (on average 1.3076923076923077) internal successors, (34), 29 states have internal predecessors, (34), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) Second operand has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-23 15:23:59,418 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 15:23:59,418 INFO L93 Difference]: Finished difference Result 90 states and 136 transitions. [2023-11-23 15:23:59,420 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-23 15:23:59,421 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 15 [2023-11-23 15:23:59,421 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 15:23:59,427 INFO L225 Difference]: With dead ends: 90 [2023-11-23 15:23:59,427 INFO L226 Difference]: Without dead ends: 46 [2023-11-23 15:23:59,430 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-23 15:23:59,438 INFO L413 NwaCegarLoop]: 33 mSDtfsCounter, 19 mSDsluCounter, 7 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 40 SdHoareTripleChecker+Invalid, 49 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-23 15:23:59,440 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 40 Invalid, 49 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-23 15:23:59,453 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2023-11-23 15:23:59,474 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 42. [2023-11-23 15:23:59,475 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 42 states, 25 states have (on average 1.16) internal successors, (29), 28 states have internal predecessors, (29), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2023-11-23 15:23:59,478 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 54 transitions. [2023-11-23 15:23:59,479 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 54 transitions. Word has length 15 [2023-11-23 15:23:59,479 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 15:23:59,479 INFO L495 AbstractCegarLoop]: Abstraction has 42 states and 54 transitions. [2023-11-23 15:23:59,479 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-23 15:23:59,480 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 54 transitions. [2023-11-23 15:23:59,480 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2023-11-23 15:23:59,480 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 15:23:59,480 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 15:23:59,481 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-11-23 15:23:59,481 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 15:23:59,482 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 15:23:59,482 INFO L85 PathProgramCache]: Analyzing trace with hash 318761401, now seen corresponding path program 1 times [2023-11-23 15:23:59,482 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 15:23:59,483 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [173614242] [2023-11-23 15:23:59,483 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 15:23:59,483 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 15:23:59,579 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 15:24:00,389 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-23 15:24:00,394 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 15:24:00,558 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-23 15:24:00,558 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 15:24:00,558 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [173614242] [2023-11-23 15:24:00,558 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [173614242] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-23 15:24:00,558 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-23 15:24:00,559 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [] total 13 [2023-11-23 15:24:00,559 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1591991898] [2023-11-23 15:24:00,559 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-23 15:24:00,560 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-11-23 15:24:00,563 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 15:24:00,563 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-11-23 15:24:00,563 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=129, Unknown=0, NotChecked=0, Total=156 [2023-11-23 15:24:00,564 INFO L87 Difference]: Start difference. First operand 42 states and 54 transitions. Second operand has 13 states, 10 states have (on average 1.2) internal successors, (12), 9 states have internal predecessors, (12), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-23 15:24:01,159 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 15:24:01,159 INFO L93 Difference]: Finished difference Result 76 states and 99 transitions. [2023-11-23 15:24:01,159 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2023-11-23 15:24:01,159 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 10 states have (on average 1.2) internal successors, (12), 9 states have internal predecessors, (12), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 16 [2023-11-23 15:24:01,160 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 15:24:01,161 INFO L225 Difference]: With dead ends: 76 [2023-11-23 15:24:01,161 INFO L226 Difference]: Without dead ends: 74 [2023-11-23 15:24:01,161 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 21 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 41 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=70, Invalid=350, Unknown=0, NotChecked=0, Total=420 [2023-11-23 15:24:01,162 INFO L413 NwaCegarLoop]: 22 mSDtfsCounter, 62 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 389 mSolverCounterSat, 46 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 70 SdHoareTripleChecker+Valid, 113 SdHoareTripleChecker+Invalid, 435 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 46 IncrementalHoareTripleChecker+Valid, 389 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-11-23 15:24:01,162 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [70 Valid, 113 Invalid, 435 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [46 Valid, 389 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-11-23 15:24:01,163 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2023-11-23 15:24:01,172 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 68. [2023-11-23 15:24:01,172 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 68 states, 40 states have (on average 1.125) internal successors, (45), 43 states have internal predecessors, (45), 20 states have call successors, (20), 5 states have call predecessors, (20), 7 states have return successors, (24), 19 states have call predecessors, (24), 19 states have call successors, (24) [2023-11-23 15:24:01,173 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 68 states to 68 states and 89 transitions. [2023-11-23 15:24:01,173 INFO L78 Accepts]: Start accepts. Automaton has 68 states and 89 transitions. Word has length 16 [2023-11-23 15:24:01,173 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 15:24:01,173 INFO L495 AbstractCegarLoop]: Abstraction has 68 states and 89 transitions. [2023-11-23 15:24:01,173 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 10 states have (on average 1.2) internal successors, (12), 9 states have internal predecessors, (12), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-23 15:24:01,173 INFO L276 IsEmpty]: Start isEmpty. Operand 68 states and 89 transitions. [2023-11-23 15:24:01,174 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2023-11-23 15:24:01,174 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 15:24:01,174 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 15:24:01,174 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-11-23 15:24:01,174 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 15:24:01,174 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 15:24:01,175 INFO L85 PathProgramCache]: Analyzing trace with hash -210214075, now seen corresponding path program 1 times [2023-11-23 15:24:01,175 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 15:24:01,175 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1784281313] [2023-11-23 15:24:01,175 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 15:24:01,175 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 15:24:01,187 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 15:24:01,188 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [882984389] [2023-11-23 15:24:01,188 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 15:24:01,188 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 15:24:01,188 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 15:24:01,189 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-11-23 15:24:01,193 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-11-23 15:24:01,449 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 15:24:01,452 INFO L262 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 51 conjunts are in the unsatisfiable core [2023-11-23 15:24:01,457 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 15:24:01,487 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-11-23 15:24:01,492 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-11-23 15:24:01,495 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-11-23 15:24:01,636 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-11-23 15:24:01,643 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-11-23 15:24:01,646 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-11-23 15:24:01,694 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-23 15:24:01,694 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 15:24:04,417 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 15:24:04,417 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1784281313] [2023-11-23 15:24:04,418 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 15:24:04,418 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [882984389] [2023-11-23 15:24:04,418 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [882984389] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 15:24:04,418 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-11-23 15:24:04,418 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2023-11-23 15:24:04,418 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [807977230] [2023-11-23 15:24:04,419 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-11-23 15:24:04,419 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2023-11-23 15:24:04,419 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 15:24:04,419 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2023-11-23 15:24:04,420 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=85, Unknown=1, NotChecked=0, Total=110 [2023-11-23 15:24:04,420 INFO L87 Difference]: Start difference. First operand 68 states and 89 transitions. Second operand has 9 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 7 states have internal predecessors, (16), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-23 15:24:04,722 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 15:24:04,722 INFO L93 Difference]: Finished difference Result 115 states and 151 transitions. [2023-11-23 15:24:04,722 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-11-23 15:24:04,723 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 7 states have internal predecessors, (16), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 22 [2023-11-23 15:24:04,723 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 15:24:04,724 INFO L225 Difference]: With dead ends: 115 [2023-11-23 15:24:04,724 INFO L226 Difference]: Without dead ends: 113 [2023-11-23 15:24:04,725 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 31 GetRequests, 13 SyntacticMatches, 5 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 30 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=49, Invalid=160, Unknown=1, NotChecked=0, Total=210 [2023-11-23 15:24:04,725 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 50 mSDsluCounter, 153 mSDsCounter, 0 mSdLazyCounter, 231 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 52 SdHoareTripleChecker+Valid, 184 SdHoareTripleChecker+Invalid, 260 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 231 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-23 15:24:04,726 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [52 Valid, 184 Invalid, 260 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 231 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-23 15:24:04,726 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 113 states. [2023-11-23 15:24:04,756 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 113 to 103. [2023-11-23 15:24:04,757 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 103 states, 61 states have (on average 1.1311475409836065) internal successors, (69), 65 states have internal predecessors, (69), 30 states have call successors, (30), 8 states have call predecessors, (30), 11 states have return successors, (37), 29 states have call predecessors, (37), 28 states have call successors, (37) [2023-11-23 15:24:04,758 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 103 states to 103 states and 136 transitions. [2023-11-23 15:24:04,758 INFO L78 Accepts]: Start accepts. Automaton has 103 states and 136 transitions. Word has length 22 [2023-11-23 15:24:04,758 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 15:24:04,758 INFO L495 AbstractCegarLoop]: Abstraction has 103 states and 136 transitions. [2023-11-23 15:24:04,758 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 7 states have internal predecessors, (16), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-23 15:24:04,759 INFO L276 IsEmpty]: Start isEmpty. Operand 103 states and 136 transitions. [2023-11-23 15:24:04,759 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2023-11-23 15:24:04,759 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 15:24:04,759 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 15:24:04,765 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2023-11-23 15:24:04,964 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 15:24:04,965 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 15:24:04,965 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 15:24:04,965 INFO L85 PathProgramCache]: Analyzing trace with hash 661147168, now seen corresponding path program 1 times [2023-11-23 15:24:04,965 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 15:24:04,966 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1366082667] [2023-11-23 15:24:04,966 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 15:24:04,966 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 15:24:04,993 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 15:24:05,571 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-23 15:24:05,589 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 15:24:05,858 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-23 15:24:05,862 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 15:24:06,018 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-11-23 15:24:06,018 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 15:24:06,019 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1366082667] [2023-11-23 15:24:06,019 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1366082667] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 15:24:06,019 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1320952566] [2023-11-23 15:24:06,019 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 15:24:06,019 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 15:24:06,019 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 15:24:06,033 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-11-23 15:24:06,066 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-11-23 15:24:06,163 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 15:24:06,166 INFO L262 TraceCheckSpWp]: Trace formula consists of 217 conjuncts, 95 conjunts are in the unsatisfiable core [2023-11-23 15:24:06,169 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 15:24:06,175 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-11-23 15:24:06,178 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-11-23 15:24:06,182 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-11-23 15:24:06,186 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-11-23 15:24:06,540 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-11-23 15:24:06,555 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-23 15:24:06,555 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 32 treesize of output 32 [2023-11-23 15:24:06,714 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-11-23 15:24:06,799 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-11-23 15:24:06,799 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 15:24:07,496 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1320952566] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 15:24:07,496 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-23 15:24:07,497 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 15] total 28 [2023-11-23 15:24:07,497 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [150657845] [2023-11-23 15:24:07,497 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-23 15:24:07,497 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2023-11-23 15:24:07,497 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 15:24:07,498 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2023-11-23 15:24:07,498 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=98, Invalid=1092, Unknown=0, NotChecked=0, Total=1190 [2023-11-23 15:24:07,498 INFO L87 Difference]: Start difference. First operand 103 states and 136 transitions. Second operand has 28 states, 21 states have (on average 1.2380952380952381) internal successors, (26), 20 states have internal predecessors, (26), 7 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2023-11-23 15:24:10,388 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-11-23 15:24:13,903 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 15:24:13,903 INFO L93 Difference]: Finished difference Result 151 states and 196 transitions. [2023-11-23 15:24:13,903 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2023-11-23 15:24:13,904 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 21 states have (on average 1.2380952380952381) internal successors, (26), 20 states have internal predecessors, (26), 7 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) Word has length 22 [2023-11-23 15:24:13,904 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 15:24:13,905 INFO L225 Difference]: With dead ends: 151 [2023-11-23 15:24:13,906 INFO L226 Difference]: Without dead ends: 149 [2023-11-23 15:24:13,907 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 67 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 50 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 378 ImplicationChecksByTransitivity, 3.8s TimeCoverageRelationStatistics Valid=238, Invalid=2413, Unknown=1, NotChecked=0, Total=2652 [2023-11-23 15:24:13,907 INFO L413 NwaCegarLoop]: 40 mSDtfsCounter, 107 mSDsluCounter, 308 mSDsCounter, 0 mSdLazyCounter, 1709 mSolverCounterSat, 72 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 119 SdHoareTripleChecker+Valid, 348 SdHoareTripleChecker+Invalid, 1782 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 72 IncrementalHoareTripleChecker+Valid, 1709 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.5s IncrementalHoareTripleChecker+Time [2023-11-23 15:24:13,907 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [119 Valid, 348 Invalid, 1782 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [72 Valid, 1709 Invalid, 1 Unknown, 0 Unchecked, 3.5s Time] [2023-11-23 15:24:13,908 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 149 states. [2023-11-23 15:24:13,923 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 149 to 140. [2023-11-23 15:24:13,923 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 140 states, 85 states have (on average 1.1294117647058823) internal successors, (96), 89 states have internal predecessors, (96), 37 states have call successors, (37), 13 states have call predecessors, (37), 17 states have return successors, (48), 37 states have call predecessors, (48), 35 states have call successors, (48) [2023-11-23 15:24:13,924 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 140 states to 140 states and 181 transitions. [2023-11-23 15:24:13,924 INFO L78 Accepts]: Start accepts. Automaton has 140 states and 181 transitions. Word has length 22 [2023-11-23 15:24:13,925 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 15:24:13,925 INFO L495 AbstractCegarLoop]: Abstraction has 140 states and 181 transitions. [2023-11-23 15:24:13,925 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 21 states have (on average 1.2380952380952381) internal successors, (26), 20 states have internal predecessors, (26), 7 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2023-11-23 15:24:13,925 INFO L276 IsEmpty]: Start isEmpty. Operand 140 states and 181 transitions. [2023-11-23 15:24:13,926 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2023-11-23 15:24:13,926 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 15:24:13,926 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 15:24:13,938 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2023-11-23 15:24:14,137 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,SelfDestructingSolverStorable3 [2023-11-23 15:24:14,138 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 15:24:14,138 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 15:24:14,138 INFO L85 PathProgramCache]: Analyzing trace with hash 466428615, now seen corresponding path program 2 times [2023-11-23 15:24:14,138 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 15:24:14,139 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1105072041] [2023-11-23 15:24:14,139 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 15:24:14,139 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 15:24:14,196 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 15:24:14,741 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-23 15:24:14,753 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 15:24:15,099 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-23 15:24:15,105 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 15:24:15,363 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-23 15:24:15,367 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 15:24:15,496 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-11-23 15:24:15,496 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 15:24:15,496 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1105072041] [2023-11-23 15:24:15,496 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1105072041] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 15:24:15,496 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [438378878] [2023-11-23 15:24:15,496 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-11-23 15:24:15,496 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 15:24:15,497 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 15:24:15,498 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-11-23 15:24:15,524 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-11-23 15:24:15,612 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-11-23 15:24:15,613 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-23 15:24:15,615 INFO L262 TraceCheckSpWp]: Trace formula consists of 246 conjuncts, 118 conjunts are in the unsatisfiable core [2023-11-23 15:24:15,617 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 15:24:15,648 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-11-23 15:24:15,691 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-11-23 15:24:15,696 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-11-23 15:24:15,915 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 8 treesize of output 1 [2023-11-23 15:24:16,356 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-23 15:24:16,356 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 40 treesize of output 40 [2023-11-23 15:24:18,552 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-11-23 15:24:18,554 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-11-23 15:24:18,664 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 4 proven. 6 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-11-23 15:24:18,664 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 15:24:19,120 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 37 treesize of output 33 [2023-11-23 15:24:19,617 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 233 treesize of output 221 [2023-11-23 15:24:19,630 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-23 15:24:19,632 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 249 treesize of output 249 [2023-11-23 15:24:20,298 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [438378878] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 15:24:20,298 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-23 15:24:20,298 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 16] total 33 [2023-11-23 15:24:20,299 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1593779167] [2023-11-23 15:24:20,299 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-23 15:24:20,299 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2023-11-23 15:24:20,299 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 15:24:20,299 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2023-11-23 15:24:20,300 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=117, Invalid=1442, Unknown=1, NotChecked=0, Total=1560 [2023-11-23 15:24:20,300 INFO L87 Difference]: Start difference. First operand 140 states and 181 transitions. Second operand has 33 states, 26 states have (on average 1.2692307692307692) internal successors, (33), 24 states have internal predecessors, (33), 8 states have call successors, (10), 7 states have call predecessors, (10), 5 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2023-11-23 15:24:23,574 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 15:24:23,574 INFO L93 Difference]: Finished difference Result 198 states and 261 transitions. [2023-11-23 15:24:23,574 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2023-11-23 15:24:23,575 INFO L78 Accepts]: Start accepts. Automaton has has 33 states, 26 states have (on average 1.2692307692307692) internal successors, (33), 24 states have internal predecessors, (33), 8 states have call successors, (10), 7 states have call predecessors, (10), 5 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) Word has length 28 [2023-11-23 15:24:23,575 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 15:24:23,577 INFO L225 Difference]: With dead ends: 198 [2023-11-23 15:24:23,577 INFO L226 Difference]: Without dead ends: 196 [2023-11-23 15:24:23,578 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 89 GetRequests, 22 SyntacticMatches, 1 SemanticMatches, 66 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 809 ImplicationChecksByTransitivity, 5.2s TimeCoverageRelationStatistics Valid=410, Invalid=4145, Unknown=1, NotChecked=0, Total=4556 [2023-11-23 15:24:23,579 INFO L413 NwaCegarLoop]: 35 mSDtfsCounter, 132 mSDsluCounter, 312 mSDsCounter, 0 mSdLazyCounter, 1959 mSolverCounterSat, 106 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 146 SdHoareTripleChecker+Valid, 347 SdHoareTripleChecker+Invalid, 2065 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 106 IncrementalHoareTripleChecker+Valid, 1959 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.7s IncrementalHoareTripleChecker+Time [2023-11-23 15:24:23,579 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [146 Valid, 347 Invalid, 2065 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [106 Valid, 1959 Invalid, 0 Unknown, 0 Unchecked, 1.7s Time] [2023-11-23 15:24:23,580 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 196 states. [2023-11-23 15:24:23,610 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 196 to 137. [2023-11-23 15:24:23,610 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 137 states, 84 states have (on average 1.130952380952381) internal successors, (95), 88 states have internal predecessors, (95), 36 states have call successors, (36), 13 states have call predecessors, (36), 16 states have return successors, (43), 35 states have call predecessors, (43), 34 states have call successors, (43) [2023-11-23 15:24:23,611 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 137 states to 137 states and 174 transitions. [2023-11-23 15:24:23,611 INFO L78 Accepts]: Start accepts. Automaton has 137 states and 174 transitions. Word has length 28 [2023-11-23 15:24:23,611 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 15:24:23,611 INFO L495 AbstractCegarLoop]: Abstraction has 137 states and 174 transitions. [2023-11-23 15:24:23,612 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 33 states, 26 states have (on average 1.2692307692307692) internal successors, (33), 24 states have internal predecessors, (33), 8 states have call successors, (10), 7 states have call predecessors, (10), 5 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2023-11-23 15:24:23,612 INFO L276 IsEmpty]: Start isEmpty. Operand 137 states and 174 transitions. [2023-11-23 15:24:23,612 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2023-11-23 15:24:23,612 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 15:24:23,613 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 15:24:23,636 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-11-23 15:24:23,822 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 15:24:23,822 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 15:24:23,823 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 15:24:23,823 INFO L85 PathProgramCache]: Analyzing trace with hash 1566657743, now seen corresponding path program 1 times [2023-11-23 15:24:23,823 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 15:24:23,823 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1186332259] [2023-11-23 15:24:23,823 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 15:24:23,823 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 15:24:23,835 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 15:24:23,838 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [584304598] [2023-11-23 15:24:23,838 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 15:24:23,838 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 15:24:23,838 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 15:24:23,853 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-11-23 15:24:23,882 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-11-23 15:24:24,001 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 15:24:24,003 INFO L262 TraceCheckSpWp]: Trace formula consists of 260 conjuncts, 89 conjunts are in the unsatisfiable core [2023-11-23 15:24:24,006 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 15:24:24,009 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-11-23 15:24:24,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-11-23 15:24:24,014 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-11-23 15:24:24,018 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-11-23 15:24:24,023 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-11-23 15:24:24,359 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-11-23 15:24:24,363 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-11-23 15:24:24,419 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-11-23 15:24:24,419 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 15:24:28,620 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 15:24:28,620 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1186332259] [2023-11-23 15:24:28,620 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 15:24:28,620 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [584304598] [2023-11-23 15:24:28,620 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [584304598] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 15:24:28,620 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-11-23 15:24:28,620 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2023-11-23 15:24:28,621 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2119220386] [2023-11-23 15:24:28,621 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-11-23 15:24:28,621 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-11-23 15:24:28,621 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 15:24:28,621 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-11-23 15:24:28,622 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=105, Unknown=1, NotChecked=0, Total=132 [2023-11-23 15:24:28,622 INFO L87 Difference]: Start difference. First operand 137 states and 174 transitions. Second operand has 10 states, 8 states have (on average 2.125) internal successors, (17), 8 states have internal predecessors, (17), 3 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2023-11-23 15:24:29,173 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 15:24:29,174 INFO L93 Difference]: Finished difference Result 155 states and 192 transitions. [2023-11-23 15:24:29,174 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-11-23 15:24:29,174 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 2.125) internal successors, (17), 8 states have internal predecessors, (17), 3 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 28 [2023-11-23 15:24:29,174 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 15:24:29,176 INFO L225 Difference]: With dead ends: 155 [2023-11-23 15:24:29,176 INFO L226 Difference]: Without dead ends: 153 [2023-11-23 15:24:29,176 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 17 SyntacticMatches, 6 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19 ImplicationChecksByTransitivity, 4.5s TimeCoverageRelationStatistics Valid=71, Invalid=234, Unknown=1, NotChecked=0, Total=306 [2023-11-23 15:24:29,177 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 46 mSDsluCounter, 163 mSDsCounter, 0 mSdLazyCounter, 312 mSolverCounterSat, 36 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 48 SdHoareTripleChecker+Valid, 187 SdHoareTripleChecker+Invalid, 348 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 36 IncrementalHoareTripleChecker+Valid, 312 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-11-23 15:24:29,177 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [48 Valid, 187 Invalid, 348 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [36 Valid, 312 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-11-23 15:24:29,179 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 153 states. [2023-11-23 15:24:29,241 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 153 to 151. [2023-11-23 15:24:29,242 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 151 states, 93 states have (on average 1.1290322580645162) internal successors, (105), 97 states have internal predecessors, (105), 39 states have call successors, (39), 15 states have call predecessors, (39), 18 states have return successors, (45), 38 states have call predecessors, (45), 36 states have call successors, (45) [2023-11-23 15:24:29,244 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 151 states to 151 states and 189 transitions. [2023-11-23 15:24:29,244 INFO L78 Accepts]: Start accepts. Automaton has 151 states and 189 transitions. Word has length 28 [2023-11-23 15:24:29,244 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 15:24:29,244 INFO L495 AbstractCegarLoop]: Abstraction has 151 states and 189 transitions. [2023-11-23 15:24:29,245 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 2.125) internal successors, (17), 8 states have internal predecessors, (17), 3 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2023-11-23 15:24:29,248 INFO L276 IsEmpty]: Start isEmpty. Operand 151 states and 189 transitions. [2023-11-23 15:24:29,252 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2023-11-23 15:24:29,253 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 15:24:29,253 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 15:24:29,265 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-11-23 15:24:29,465 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 15:24:29,465 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 15:24:29,466 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 15:24:29,466 INFO L85 PathProgramCache]: Analyzing trace with hash -858116137, now seen corresponding path program 1 times [2023-11-23 15:24:29,466 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 15:24:29,466 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [566481390] [2023-11-23 15:24:29,466 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 15:24:29,466 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 15:24:29,490 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 15:24:29,491 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [84277559] [2023-11-23 15:24:29,492 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 15:24:29,492 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 15:24:29,492 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 15:24:29,493 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-11-23 15:24:29,519 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-11-23 15:24:29,650 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 15:24:29,653 INFO L262 TraceCheckSpWp]: Trace formula consists of 323 conjuncts, 89 conjunts are in the unsatisfiable core [2023-11-23 15:24:29,655 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 15:24:29,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 15 treesize of output 1 [2023-11-23 15:24:29,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 11 treesize of output 7 [2023-11-23 15:24:29,667 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-11-23 15:24:29,671 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-11-23 15:24:29,942 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 22 [2023-11-23 15:24:29,965 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 40 treesize of output 20 [2023-11-23 15:24:29,976 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 16 [2023-11-23 15:24:30,062 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-11-23 15:24:30,062 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 15:24:39,433 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 15:24:39,433 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [566481390] [2023-11-23 15:24:39,433 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 15:24:39,433 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [84277559] [2023-11-23 15:24:39,433 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [84277559] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 15:24:39,433 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-11-23 15:24:39,433 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2023-11-23 15:24:39,433 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1479916594] [2023-11-23 15:24:39,433 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-11-23 15:24:39,434 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2023-11-23 15:24:39,434 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 15:24:39,434 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2023-11-23 15:24:39,434 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=84, Unknown=2, NotChecked=0, Total=110 [2023-11-23 15:24:39,434 INFO L87 Difference]: Start difference. First operand 151 states and 189 transitions. Second operand has 9 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 7 states have internal predecessors, (18), 3 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2023-11-23 15:24:39,823 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 15:24:39,823 INFO L93 Difference]: Finished difference Result 177 states and 214 transitions. [2023-11-23 15:24:39,824 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-11-23 15:24:39,824 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 7 states have internal predecessors, (18), 3 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 34 [2023-11-23 15:24:39,824 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 15:24:39,825 INFO L225 Difference]: With dead ends: 177 [2023-11-23 15:24:39,825 INFO L226 Difference]: Without dead ends: 175 [2023-11-23 15:24:39,825 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 21 SyntacticMatches, 9 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 36 ImplicationChecksByTransitivity, 7.5s TimeCoverageRelationStatistics Valid=49, Invalid=159, Unknown=2, NotChecked=0, Total=210 [2023-11-23 15:24:39,826 INFO L413 NwaCegarLoop]: 32 mSDtfsCounter, 34 mSDsluCounter, 158 mSDsCounter, 0 mSdLazyCounter, 207 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 36 SdHoareTripleChecker+Valid, 190 SdHoareTripleChecker+Invalid, 225 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 207 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-23 15:24:39,826 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [36 Valid, 190 Invalid, 225 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 207 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-23 15:24:39,828 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 175 states. [2023-11-23 15:24:39,854 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 175 to 173. [2023-11-23 15:24:39,855 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 173 states, 108 states have (on average 1.1203703703703705) internal successors, (121), 112 states have internal predecessors, (121), 42 states have call successors, (42), 19 states have call predecessors, (42), 22 states have return successors, (47), 41 states have call predecessors, (47), 38 states have call successors, (47) [2023-11-23 15:24:39,856 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 173 states to 173 states and 210 transitions. [2023-11-23 15:24:39,856 INFO L78 Accepts]: Start accepts. Automaton has 173 states and 210 transitions. Word has length 34 [2023-11-23 15:24:39,856 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 15:24:39,856 INFO L495 AbstractCegarLoop]: Abstraction has 173 states and 210 transitions. [2023-11-23 15:24:39,856 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 7 states have internal predecessors, (18), 3 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2023-11-23 15:24:39,857 INFO L276 IsEmpty]: Start isEmpty. Operand 173 states and 210 transitions. [2023-11-23 15:24:39,857 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2023-11-23 15:24:39,857 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 15:24:39,857 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] [2023-11-23 15:24:39,870 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-11-23 15:24:40,070 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 15:24:40,070 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 15:24:40,070 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 15:24:40,071 INFO L85 PathProgramCache]: Analyzing trace with hash 990596790, now seen corresponding path program 1 times [2023-11-23 15:24:40,071 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 15:24:40,071 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [642102749] [2023-11-23 15:24:40,071 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 15:24:40,071 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 15:24:40,095 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 15:24:40,096 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1986949724] [2023-11-23 15:24:40,096 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 15:24:40,096 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 15:24:40,096 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 15:24:40,097 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-11-23 15:24:40,099 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-11-23 15:24:40,227 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 15:24:40,229 INFO L262 TraceCheckSpWp]: Trace formula consists of 289 conjuncts, 95 conjunts are in the unsatisfiable core [2023-11-23 15:24:40,232 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 15:24:40,239 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-11-23 15:24:40,241 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-11-23 15:24:40,244 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-11-23 15:24:40,248 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-11-23 15:24:40,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 15 treesize of output 11 [2023-11-23 15:24:40,257 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-11-23 15:24:40,384 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-11-23 15:24:40,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 7 treesize of output 3 [2023-11-23 15:24:40,723 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2023-11-23 15:24:40,723 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 15:24:51,126 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 15:24:51,127 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [642102749] [2023-11-23 15:24:51,127 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 15:24:51,127 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1986949724] [2023-11-23 15:24:51,127 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1986949724] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 15:24:51,127 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-11-23 15:24:51,127 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2023-11-23 15:24:51,127 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1404791187] [2023-11-23 15:24:51,128 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-11-23 15:24:51,128 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-11-23 15:24:51,128 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 15:24:51,128 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-11-23 15:24:51,129 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=201, Unknown=3, NotChecked=0, Total=240 [2023-11-23 15:24:51,129 INFO L87 Difference]: Start difference. First operand 173 states and 210 transitions. Second operand has 14 states, 10 states have (on average 2.1) internal successors, (21), 11 states have internal predecessors, (21), 5 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2023-11-23 15:24:51,978 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 15:24:51,979 INFO L93 Difference]: Finished difference Result 225 states and 268 transitions. [2023-11-23 15:24:51,981 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2023-11-23 15:24:51,981 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 10 states have (on average 2.1) internal successors, (21), 11 states have internal predecessors, (21), 5 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Word has length 34 [2023-11-23 15:24:51,981 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 15:24:51,982 INFO L225 Difference]: With dead ends: 225 [2023-11-23 15:24:51,982 INFO L226 Difference]: Without dead ends: 223 [2023-11-23 15:24:51,983 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 45 GetRequests, 20 SyntacticMatches, 5 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 54 ImplicationChecksByTransitivity, 10.7s TimeCoverageRelationStatistics Valid=81, Invalid=378, Unknown=3, NotChecked=0, Total=462 [2023-11-23 15:24:51,983 INFO L413 NwaCegarLoop]: 44 mSDtfsCounter, 55 mSDsluCounter, 191 mSDsCounter, 0 mSdLazyCounter, 655 mSolverCounterSat, 39 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 63 SdHoareTripleChecker+Valid, 235 SdHoareTripleChecker+Invalid, 696 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 39 IncrementalHoareTripleChecker+Valid, 655 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2023-11-23 15:24:51,983 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [63 Valid, 235 Invalid, 696 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [39 Valid, 655 Invalid, 2 Unknown, 0 Unchecked, 0.6s Time] [2023-11-23 15:24:51,984 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 223 states. [2023-11-23 15:24:52,024 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 223 to 219. [2023-11-23 15:24:52,025 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 219 states, 137 states have (on average 1.1094890510948905) internal successors, (152), 141 states have internal predecessors, (152), 52 states have call successors, (52), 25 states have call predecessors, (52), 29 states have return successors, (60), 52 states have call predecessors, (60), 47 states have call successors, (60) [2023-11-23 15:24:52,031 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 219 states to 219 states and 264 transitions. [2023-11-23 15:24:52,031 INFO L78 Accepts]: Start accepts. Automaton has 219 states and 264 transitions. Word has length 34 [2023-11-23 15:24:52,031 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 15:24:52,032 INFO L495 AbstractCegarLoop]: Abstraction has 219 states and 264 transitions. [2023-11-23 15:24:52,033 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 10 states have (on average 2.1) internal successors, (21), 11 states have internal predecessors, (21), 5 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2023-11-23 15:24:52,033 INFO L276 IsEmpty]: Start isEmpty. Operand 219 states and 264 transitions. [2023-11-23 15:24:52,035 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2023-11-23 15:24:52,035 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 15:24:52,035 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 15:24:52,047 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2023-11-23 15:24:52,250 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 15:24:52,251 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 15:24:52,251 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 15:24:52,251 INFO L85 PathProgramCache]: Analyzing trace with hash -766811939, now seen corresponding path program 2 times [2023-11-23 15:24:52,252 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 15:24:52,252 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [556776532] [2023-11-23 15:24:52,252 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 15:24:52,252 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 15:24:52,265 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 15:24:52,265 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [868694354] [2023-11-23 15:24:52,265 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-11-23 15:24:52,266 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 15:24:52,266 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 15:24:52,266 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-11-23 15:24:52,267 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-11-23 15:24:52,457 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-11-23 15:24:52,457 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-23 15:24:52,460 WARN L260 TraceCheckSpWp]: Trace formula consists of 318 conjuncts, 192 conjunts are in the unsatisfiable core [2023-11-23 15:24:52,463 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 15:24:52,481 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-11-23 15:24:52,535 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-11-23 15:24:52,540 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-11-23 15:24:52,550 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-11-23 15:24:52,557 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-11-23 15:24:52,897 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-11-23 15:24:53,252 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-11-23 15:24:54,414 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-23 15:24:54,414 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 37 treesize of output 29 [2023-11-23 15:24:54,425 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-23 15:24:54,425 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 72 treesize of output 44 [2023-11-23 15:24:54,609 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 2 proven. 15 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2023-11-23 15:24:54,609 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 15:25:05,679 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 15:25:05,679 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [556776532] [2023-11-23 15:25:05,679 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 15:25:05,679 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [868694354] [2023-11-23 15:25:05,679 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [868694354] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 15:25:05,679 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-11-23 15:25:05,679 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23] total 23 [2023-11-23 15:25:05,680 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2033874298] [2023-11-23 15:25:05,680 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-11-23 15:25:05,680 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2023-11-23 15:25:05,680 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 15:25:05,681 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2023-11-23 15:25:05,681 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=75, Invalid=678, Unknown=3, NotChecked=0, Total=756 [2023-11-23 15:25:05,681 INFO L87 Difference]: Start difference. First operand 219 states and 264 transitions. Second operand has 24 states, 18 states have (on average 1.4444444444444444) internal successors, (26), 19 states have internal predecessors, (26), 7 states have call successors, (7), 4 states have call predecessors, (7), 5 states have return successors, (5), 4 states have call predecessors, (5), 5 states have call successors, (5) [2023-11-23 15:25:08,627 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 15:25:08,627 INFO L93 Difference]: Finished difference Result 271 states and 322 transitions. [2023-11-23 15:25:08,628 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2023-11-23 15:25:08,628 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 18 states have (on average 1.4444444444444444) internal successors, (26), 19 states have internal predecessors, (26), 7 states have call successors, (7), 4 states have call predecessors, (7), 5 states have return successors, (5), 4 states have call predecessors, (5), 5 states have call successors, (5) Word has length 40 [2023-11-23 15:25:08,628 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 15:25:08,629 INFO L225 Difference]: With dead ends: 271 [2023-11-23 15:25:08,629 INFO L226 Difference]: Without dead ends: 269 [2023-11-23 15:25:08,630 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 16 SyntacticMatches, 3 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 340 ImplicationChecksByTransitivity, 13.0s TimeCoverageRelationStatistics Valid=169, Invalid=1388, Unknown=3, NotChecked=0, Total=1560 [2023-11-23 15:25:08,630 INFO L413 NwaCegarLoop]: 39 mSDtfsCounter, 63 mSDsluCounter, 230 mSDsCounter, 0 mSdLazyCounter, 1320 mSolverCounterSat, 44 mSolverCounterUnsat, 3 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 74 SdHoareTripleChecker+Valid, 269 SdHoareTripleChecker+Invalid, 1367 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 44 IncrementalHoareTripleChecker+Valid, 1320 IncrementalHoareTripleChecker+Invalid, 3 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.9s IncrementalHoareTripleChecker+Time [2023-11-23 15:25:08,630 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [74 Valid, 269 Invalid, 1367 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [44 Valid, 1320 Invalid, 3 Unknown, 0 Unchecked, 1.9s Time] [2023-11-23 15:25:08,630 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 269 states. [2023-11-23 15:25:08,708 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 269 to 221. [2023-11-23 15:25:08,708 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 221 states, 138 states have (on average 1.108695652173913) internal successors, (153), 142 states have internal predecessors, (153), 52 states have call successors, (52), 25 states have call predecessors, (52), 30 states have return successors, (62), 53 states have call predecessors, (62), 47 states have call successors, (62) [2023-11-23 15:25:08,709 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 221 states to 221 states and 267 transitions. [2023-11-23 15:25:08,710 INFO L78 Accepts]: Start accepts. Automaton has 221 states and 267 transitions. Word has length 40 [2023-11-23 15:25:08,710 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 15:25:08,710 INFO L495 AbstractCegarLoop]: Abstraction has 221 states and 267 transitions. [2023-11-23 15:25:08,710 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 18 states have (on average 1.4444444444444444) internal successors, (26), 19 states have internal predecessors, (26), 7 states have call successors, (7), 4 states have call predecessors, (7), 5 states have return successors, (5), 4 states have call predecessors, (5), 5 states have call successors, (5) [2023-11-23 15:25:08,710 INFO L276 IsEmpty]: Start isEmpty. Operand 221 states and 267 transitions. [2023-11-23 15:25:08,711 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2023-11-23 15:25:08,711 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 15:25:08,711 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 15:25:08,723 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2023-11-23 15:25:08,923 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 15:25:08,923 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 15:25:08,923 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 15:25:08,923 INFO L85 PathProgramCache]: Analyzing trace with hash 1584657220, now seen corresponding path program 3 times [2023-11-23 15:25:08,923 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 15:25:08,923 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1314744834] [2023-11-23 15:25:08,923 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 15:25:08,924 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 15:25:08,935 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 15:25:08,936 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1989036616] [2023-11-23 15:25:08,936 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-23 15:25:08,936 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 15:25:08,936 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 15:25:08,937 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-11-23 15:25:08,938 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-11-23 15:25:09,081 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2023-11-23 15:25:09,081 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-23 15:25:09,083 INFO L262 TraceCheckSpWp]: Trace formula consists of 268 conjuncts, 84 conjunts are in the unsatisfiable core [2023-11-23 15:25:09,086 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 15:25:09,090 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 20 [2023-11-23 15:25:09,118 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 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-11-23 15:25:09,121 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 1 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-11-23 15:25:09,124 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 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-11-23 15:25:09,128 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 2 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-11-23 15:25:09,508 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 1 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-11-23 15:25:09,514 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-11-23 15:25:09,569 INFO L134 CoverageAnalysis]: Checked inductivity of 41 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 37 trivial. 0 not checked. [2023-11-23 15:25:09,570 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 15:25:09,638 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 83 treesize of output 71 [2023-11-23 15:25:10,911 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 15:25:10,912 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1314744834] [2023-11-23 15:25:10,912 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 15:25:10,912 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1989036616] [2023-11-23 15:25:10,912 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1989036616] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 15:25:10,912 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-11-23 15:25:10,912 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2023-11-23 15:25:10,915 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1477952158] [2023-11-23 15:25:10,915 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-11-23 15:25:10,915 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-11-23 15:25:10,915 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 15:25:10,916 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-11-23 15:25:10,916 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=32, Invalid=150, Unknown=0, NotChecked=0, Total=182 [2023-11-23 15:25:10,916 INFO L87 Difference]: Start difference. First operand 221 states and 267 transitions. Second operand has 10 states, 8 states have (on average 2.25) internal successors, (18), 7 states have internal predecessors, (18), 4 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2023-11-23 15:25:11,343 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 15:25:11,344 INFO L93 Difference]: Finished difference Result 229 states and 273 transitions. [2023-11-23 15:25:11,344 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-11-23 15:25:11,344 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 2.25) internal successors, (18), 7 states have internal predecessors, (18), 4 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Word has length 46 [2023-11-23 15:25:11,346 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 15:25:11,347 INFO L225 Difference]: With dead ends: 229 [2023-11-23 15:25:11,347 INFO L226 Difference]: Without dead ends: 227 [2023-11-23 15:25:11,349 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 56 GetRequests, 34 SyntacticMatches, 5 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 44 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=65, Invalid=277, Unknown=0, NotChecked=0, Total=342 [2023-11-23 15:25:11,350 INFO L413 NwaCegarLoop]: 32 mSDtfsCounter, 44 mSDsluCounter, 184 mSDsCounter, 0 mSdLazyCounter, 218 mSolverCounterSat, 27 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 46 SdHoareTripleChecker+Valid, 216 SdHoareTripleChecker+Invalid, 245 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 27 IncrementalHoareTripleChecker+Valid, 218 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-11-23 15:25:11,351 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [46 Valid, 216 Invalid, 245 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [27 Valid, 218 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-11-23 15:25:11,352 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 227 states. [2023-11-23 15:25:11,408 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 227 to 177. [2023-11-23 15:25:11,409 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 177 states, 111 states have (on average 1.117117117117117) internal successors, (124), 115 states have internal predecessors, (124), 42 states have call successors, (42), 20 states have call predecessors, (42), 23 states have return successors, (47), 41 states have call predecessors, (47), 38 states have call successors, (47) [2023-11-23 15:25:11,409 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 177 states to 177 states and 213 transitions. [2023-11-23 15:25:11,410 INFO L78 Accepts]: Start accepts. Automaton has 177 states and 213 transitions. Word has length 46 [2023-11-23 15:25:11,410 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 15:25:11,410 INFO L495 AbstractCegarLoop]: Abstraction has 177 states and 213 transitions. [2023-11-23 15:25:11,410 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 2.25) internal successors, (18), 7 states have internal predecessors, (18), 4 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2023-11-23 15:25:11,410 INFO L276 IsEmpty]: Start isEmpty. Operand 177 states and 213 transitions. [2023-11-23 15:25:11,410 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2023-11-23 15:25:11,410 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 15:25:11,411 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 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-11-23 15:25:11,421 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2023-11-23 15:25:11,616 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,SelfDestructingSolverStorable9 [2023-11-23 15:25:11,617 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 15:25:11,617 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 15:25:11,617 INFO L85 PathProgramCache]: Analyzing trace with hash -1818921507, now seen corresponding path program 1 times [2023-11-23 15:25:11,617 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 15:25:11,617 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [207751405] [2023-11-23 15:25:11,617 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 15:25:11,617 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 15:25:11,627 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 15:25:11,627 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [838479616] [2023-11-23 15:25:11,627 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 15:25:11,627 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 15:25:11,627 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 15:25:11,628 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-11-23 15:25:11,674 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-11-23 15:25:11,819 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 15:25:11,821 INFO L262 TraceCheckSpWp]: Trace formula consists of 368 conjuncts, 101 conjunts are in the unsatisfiable core [2023-11-23 15:25:11,824 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 15:25:11,828 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-11-23 15:25:11,831 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-11-23 15:25:11,834 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-11-23 15:25:11,839 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-11-23 15:25:11,843 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-11-23 15:25:12,269 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-11-23 15:25:12,275 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-11-23 15:25:12,357 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-11-23 15:25:12,357 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 15:25:17,323 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 15:25:17,324 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [207751405] [2023-11-23 15:25:17,324 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 15:25:17,324 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [838479616] [2023-11-23 15:25:17,324 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [838479616] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 15:25:17,324 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-11-23 15:25:17,324 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2023-11-23 15:25:17,325 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [711281513] [2023-11-23 15:25:17,325 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-11-23 15:25:17,325 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-11-23 15:25:17,325 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 15:25:17,326 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-11-23 15:25:17,326 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=105, Unknown=1, NotChecked=0, Total=132 [2023-11-23 15:25:17,326 INFO L87 Difference]: Start difference. First operand 177 states and 213 transitions. Second operand has 10 states, 8 states have (on average 2.375) internal successors, (19), 8 states have internal predecessors, (19), 3 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2023-11-23 15:25:17,973 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 15:25:17,973 INFO L93 Difference]: Finished difference Result 185 states and 219 transitions. [2023-11-23 15:25:17,974 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-11-23 15:25:17,974 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 2.375) internal successors, (19), 8 states have internal predecessors, (19), 3 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 40 [2023-11-23 15:25:17,974 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 15:25:17,975 INFO L225 Difference]: With dead ends: 185 [2023-11-23 15:25:17,975 INFO L226 Difference]: Without dead ends: 183 [2023-11-23 15:25:17,975 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 25 SyntacticMatches, 10 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 22 ImplicationChecksByTransitivity, 3.3s TimeCoverageRelationStatistics Valid=71, Invalid=234, Unknown=1, NotChecked=0, Total=306 [2023-11-23 15:25:17,975 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 47 mSDsluCounter, 140 mSDsCounter, 0 mSdLazyCounter, 291 mSolverCounterSat, 35 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 49 SdHoareTripleChecker+Valid, 164 SdHoareTripleChecker+Invalid, 326 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 35 IncrementalHoareTripleChecker+Valid, 291 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-11-23 15:25:17,976 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [49 Valid, 164 Invalid, 326 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [35 Valid, 291 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-11-23 15:25:17,976 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 183 states. [2023-11-23 15:25:18,007 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 183 to 181. [2023-11-23 15:25:18,007 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 181 states, 114 states have (on average 1.1140350877192982) internal successors, (127), 118 states have internal predecessors, (127), 42 states have call successors, (42), 21 states have call predecessors, (42), 24 states have return successors, (47), 41 states have call predecessors, (47), 38 states have call successors, (47) [2023-11-23 15:25:18,008 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 181 states to 181 states and 216 transitions. [2023-11-23 15:25:18,008 INFO L78 Accepts]: Start accepts. Automaton has 181 states and 216 transitions. Word has length 40 [2023-11-23 15:25:18,008 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 15:25:18,008 INFO L495 AbstractCegarLoop]: Abstraction has 181 states and 216 transitions. [2023-11-23 15:25:18,009 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 2.375) internal successors, (19), 8 states have internal predecessors, (19), 3 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2023-11-23 15:25:18,009 INFO L276 IsEmpty]: Start isEmpty. Operand 181 states and 216 transitions. [2023-11-23 15:25:18,009 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2023-11-23 15:25:18,009 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 15:25:18,009 INFO L195 NwaCegarLoop]: trace histogram [6, 5, 5, 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-11-23 15:25:18,022 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-11-23 15:25:18,222 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 15:25:18,222 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 15:25:18,222 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 15:25:18,222 INFO L85 PathProgramCache]: Analyzing trace with hash 1462790241, now seen corresponding path program 1 times [2023-11-23 15:25:18,222 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 15:25:18,223 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1244172742] [2023-11-23 15:25:18,223 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 15:25:18,223 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 15:25:18,234 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 15:25:18,234 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1224934509] [2023-11-23 15:25:18,234 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 15:25:18,235 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 15:25:18,236 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 15:25:18,237 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-11-23 15:25:18,259 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-11-23 15:25:18,395 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 15:25:18,397 INFO L262 TraceCheckSpWp]: Trace formula consists of 389 conjuncts, 88 conjunts are in the unsatisfiable core [2023-11-23 15:25:18,400 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 15:25:18,403 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-11-23 15:25:18,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-11-23 15:25:18,409 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-11-23 15:25:18,413 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-11-23 15:25:19,313 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-23 15:25:19,313 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 30 treesize of output 30 [2023-11-23 15:25:19,321 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-23 15:25:19,322 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 40 treesize of output 36 [2023-11-23 15:25:19,375 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2023-11-23 15:25:19,375 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 15:25:19,464 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 15:25:19,464 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1244172742] [2023-11-23 15:25:19,464 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 15:25:19,465 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1224934509] [2023-11-23 15:25:19,465 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1224934509] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 15:25:19,465 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-11-23 15:25:19,465 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2023-11-23 15:25:19,465 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1747501050] [2023-11-23 15:25:19,465 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-11-23 15:25:19,465 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-11-23 15:25:19,465 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 15:25:19,466 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-11-23 15:25:19,466 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=202, Unknown=0, NotChecked=0, Total=240 [2023-11-23 15:25:19,466 INFO L87 Difference]: Start difference. First operand 181 states and 216 transitions. Second operand has 14 states, 11 states have (on average 1.8181818181818181) internal successors, (20), 10 states have internal predecessors, (20), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2023-11-23 15:25:20,293 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 15:25:20,293 INFO L93 Difference]: Finished difference Result 185 states and 218 transitions. [2023-11-23 15:25:20,293 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2023-11-23 15:25:20,293 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 11 states have (on average 1.8181818181818181) internal successors, (20), 10 states have internal predecessors, (20), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 46 [2023-11-23 15:25:20,294 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 15:25:20,294 INFO L225 Difference]: With dead ends: 185 [2023-11-23 15:25:20,294 INFO L226 Difference]: Without dead ends: 183 [2023-11-23 15:25:20,295 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 59 GetRequests, 26 SyntacticMatches, 11 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 128 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=93, Invalid=459, Unknown=0, NotChecked=0, Total=552 [2023-11-23 15:25:20,295 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 45 mSDsluCounter, 168 mSDsCounter, 0 mSdLazyCounter, 475 mSolverCounterSat, 32 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 47 SdHoareTripleChecker+Valid, 193 SdHoareTripleChecker+Invalid, 507 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 32 IncrementalHoareTripleChecker+Valid, 475 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2023-11-23 15:25:20,295 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [47 Valid, 193 Invalid, 507 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [32 Valid, 475 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2023-11-23 15:25:20,295 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 183 states. [2023-11-23 15:25:20,327 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 183 to 181. [2023-11-23 15:25:20,328 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 181 states, 114 states have (on average 1.105263157894737) internal successors, (126), 118 states have internal predecessors, (126), 42 states have call successors, (42), 21 states have call predecessors, (42), 24 states have return successors, (47), 41 states have call predecessors, (47), 38 states have call successors, (47) [2023-11-23 15:25:20,329 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 181 states to 181 states and 215 transitions. [2023-11-23 15:25:20,329 INFO L78 Accepts]: Start accepts. Automaton has 181 states and 215 transitions. Word has length 46 [2023-11-23 15:25:20,329 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 15:25:20,329 INFO L495 AbstractCegarLoop]: Abstraction has 181 states and 215 transitions. [2023-11-23 15:25:20,329 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 11 states have (on average 1.8181818181818181) internal successors, (20), 10 states have internal predecessors, (20), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2023-11-23 15:25:20,329 INFO L276 IsEmpty]: Start isEmpty. Operand 181 states and 215 transitions. [2023-11-23 15:25:20,330 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2023-11-23 15:25:20,330 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 15:25:20,330 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 15:25:20,344 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2023-11-23 15:25:20,542 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,SelfDestructingSolverStorable11 [2023-11-23 15:25:20,542 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 15:25:20,542 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 15:25:20,543 INFO L85 PathProgramCache]: Analyzing trace with hash -41888444, now seen corresponding path program 1 times [2023-11-23 15:25:20,543 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 15:25:20,543 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [460678434] [2023-11-23 15:25:20,543 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 15:25:20,543 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 15:25:20,553 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 15:25:20,553 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1305530386] [2023-11-23 15:25:20,553 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 15:25:20,553 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 15:25:20,553 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 15:25:20,554 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-11-23 15:25:20,556 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-11-23 15:25:20,812 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 15:25:20,815 INFO L262 TraceCheckSpWp]: Trace formula consists of 397 conjuncts, 67 conjunts are in the unsatisfiable core [2023-11-23 15:25:20,817 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 15:25:20,820 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-11-23 15:25:20,823 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-11-23 15:25:20,826 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-11-23 15:25:20,926 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-11-23 15:25:21,416 INFO L134 CoverageAnalysis]: Checked inductivity of 37 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2023-11-23 15:25:21,417 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 15:25:31,722 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 15:25:31,722 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [460678434] [2023-11-23 15:25:31,722 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 15:25:31,722 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1305530386] [2023-11-23 15:25:31,722 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1305530386] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 15:25:31,722 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-11-23 15:25:31,722 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2023-11-23 15:25:31,722 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [577024631] [2023-11-23 15:25:31,722 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-11-23 15:25:31,722 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-11-23 15:25:31,722 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 15:25:31,723 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-11-23 15:25:31,723 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=175, Unknown=2, NotChecked=0, Total=210 [2023-11-23 15:25:31,723 INFO L87 Difference]: Start difference. First operand 181 states and 215 transitions. Second operand has 13 states, 10 states have (on average 2.3) internal successors, (23), 10 states have internal predecessors, (23), 5 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2023-11-23 15:25:32,651 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 15:25:32,651 INFO L93 Difference]: Finished difference Result 235 states and 275 transitions. [2023-11-23 15:25:32,652 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2023-11-23 15:25:32,652 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 10 states have (on average 2.3) internal successors, (23), 10 states have internal predecessors, (23), 5 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) Word has length 46 [2023-11-23 15:25:32,652 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 15:25:32,653 INFO L225 Difference]: With dead ends: 235 [2023-11-23 15:25:32,653 INFO L226 Difference]: Without dead ends: 233 [2023-11-23 15:25:32,654 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 29 SyntacticMatches, 9 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 48 ImplicationChecksByTransitivity, 10.7s TimeCoverageRelationStatistics Valid=78, Invalid=340, Unknown=2, NotChecked=0, Total=420 [2023-11-23 15:25:32,654 INFO L413 NwaCegarLoop]: 44 mSDtfsCounter, 50 mSDsluCounter, 185 mSDsCounter, 0 mSdLazyCounter, 613 mSolverCounterSat, 32 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 58 SdHoareTripleChecker+Valid, 229 SdHoareTripleChecker+Invalid, 647 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 32 IncrementalHoareTripleChecker+Valid, 613 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2023-11-23 15:25:32,654 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [58 Valid, 229 Invalid, 647 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [32 Valid, 613 Invalid, 2 Unknown, 0 Unchecked, 0.7s Time] [2023-11-23 15:25:32,655 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 233 states. [2023-11-23 15:25:32,700 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 233 to 231. [2023-11-23 15:25:32,701 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 231 states, 146 states have (on average 1.095890410958904) internal successors, (160), 150 states have internal predecessors, (160), 52 states have call successors, (52), 28 states have call predecessors, (52), 32 states have return successors, (60), 52 states have call predecessors, (60), 47 states have call successors, (60) [2023-11-23 15:25:32,702 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 231 states to 231 states and 272 transitions. [2023-11-23 15:25:32,702 INFO L78 Accepts]: Start accepts. Automaton has 231 states and 272 transitions. Word has length 46 [2023-11-23 15:25:32,702 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 15:25:32,702 INFO L495 AbstractCegarLoop]: Abstraction has 231 states and 272 transitions. [2023-11-23 15:25:32,702 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 10 states have (on average 2.3) internal successors, (23), 10 states have internal predecessors, (23), 5 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2023-11-23 15:25:32,703 INFO L276 IsEmpty]: Start isEmpty. Operand 231 states and 272 transitions. [2023-11-23 15:25:32,703 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2023-11-23 15:25:32,703 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 15:25:32,703 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 15:25:32,716 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2023-11-23 15:25:32,916 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,SelfDestructingSolverStorable12 [2023-11-23 15:25:32,916 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 15:25:32,916 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 15:25:32,916 INFO L85 PathProgramCache]: Analyzing trace with hash 1093395691, now seen corresponding path program 2 times [2023-11-23 15:25:32,916 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 15:25:32,916 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [367486167] [2023-11-23 15:25:32,917 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 15:25:32,917 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 15:25:32,945 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 15:25:32,952 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2090226771] [2023-11-23 15:25:32,952 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-11-23 15:25:32,952 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 15:25:32,953 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 15:25:32,954 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-11-23 15:25:32,977 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-11-23 15:25:33,259 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-11-23 15:25:33,259 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-23 15:25:33,262 INFO L262 TraceCheckSpWp]: Trace formula consists of 426 conjuncts, 154 conjunts are in the unsatisfiable core [2023-11-23 15:25:33,266 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 15:25:33,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-11-23 15:25:33,295 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-11-23 15:25:33,299 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-11-23 15:25:33,306 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-11-23 15:25:33,314 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-11-23 15:25:33,573 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-11-23 15:25:34,551 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-23 15:25:34,551 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 30 treesize of output 30 [2023-11-23 15:25:34,582 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-23 15:25:34,583 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 31 treesize of output 27 [2023-11-23 15:25:34,695 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 6 proven. 22 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2023-11-23 15:25:34,696 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 15:25:40,980 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 15:25:40,980 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [367486167] [2023-11-23 15:25:40,980 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 15:25:40,980 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2090226771] [2023-11-23 15:25:40,980 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2090226771] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 15:25:40,980 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-11-23 15:25:40,980 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18] total 18 [2023-11-23 15:25:40,980 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1844831353] [2023-11-23 15:25:40,980 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-11-23 15:25:40,981 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2023-11-23 15:25:40,982 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 15:25:40,982 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2023-11-23 15:25:40,982 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=364, Unknown=3, NotChecked=0, Total=420 [2023-11-23 15:25:40,982 INFO L87 Difference]: Start difference. First operand 231 states and 272 transitions. Second operand has 19 states, 14 states have (on average 2.0) internal successors, (28), 15 states have internal predecessors, (28), 7 states have call successors, (9), 4 states have call predecessors, (9), 5 states have return successors, (7), 4 states have call predecessors, (7), 5 states have call successors, (7) [2023-11-23 15:25:45,140 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 15:25:45,140 INFO L93 Difference]: Finished difference Result 285 states and 332 transitions. [2023-11-23 15:25:45,140 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2023-11-23 15:25:45,141 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 14 states have (on average 2.0) internal successors, (28), 15 states have internal predecessors, (28), 7 states have call successors, (9), 4 states have call predecessors, (9), 5 states have return successors, (7), 4 states have call predecessors, (7), 5 states have call successors, (7) Word has length 52 [2023-11-23 15:25:45,141 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 15:25:45,142 INFO L225 Difference]: With dead ends: 285 [2023-11-23 15:25:45,142 INFO L226 Difference]: Without dead ends: 283 [2023-11-23 15:25:45,142 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 66 GetRequests, 29 SyntacticMatches, 9 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 188 ImplicationChecksByTransitivity, 9.4s TimeCoverageRelationStatistics Valid=128, Invalid=738, Unknown=4, NotChecked=0, Total=870 [2023-11-23 15:25:45,143 INFO L413 NwaCegarLoop]: 41 mSDtfsCounter, 51 mSDsluCounter, 303 mSDsCounter, 0 mSdLazyCounter, 1072 mSolverCounterSat, 35 mSolverCounterUnsat, 4 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 62 SdHoareTripleChecker+Valid, 344 SdHoareTripleChecker+Invalid, 1111 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 35 IncrementalHoareTripleChecker+Valid, 1072 IncrementalHoareTripleChecker+Invalid, 4 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.4s IncrementalHoareTripleChecker+Time [2023-11-23 15:25:45,143 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [62 Valid, 344 Invalid, 1111 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [35 Valid, 1072 Invalid, 4 Unknown, 0 Unchecked, 1.4s Time] [2023-11-23 15:25:45,143 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 283 states. [2023-11-23 15:25:45,239 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 283 to 233. [2023-11-23 15:25:45,239 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 233 states, 147 states have (on average 1.0952380952380953) internal successors, (161), 151 states have internal predecessors, (161), 52 states have call successors, (52), 28 states have call predecessors, (52), 33 states have return successors, (62), 53 states have call predecessors, (62), 47 states have call successors, (62) [2023-11-23 15:25:45,240 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 233 states to 233 states and 275 transitions. [2023-11-23 15:25:45,240 INFO L78 Accepts]: Start accepts. Automaton has 233 states and 275 transitions. Word has length 52 [2023-11-23 15:25:45,240 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 15:25:45,241 INFO L495 AbstractCegarLoop]: Abstraction has 233 states and 275 transitions. [2023-11-23 15:25:45,241 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 14 states have (on average 2.0) internal successors, (28), 15 states have internal predecessors, (28), 7 states have call successors, (9), 4 states have call predecessors, (9), 5 states have return successors, (7), 4 states have call predecessors, (7), 5 states have call successors, (7) [2023-11-23 15:25:45,241 INFO L276 IsEmpty]: Start isEmpty. Operand 233 states and 275 transitions. [2023-11-23 15:25:45,241 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2023-11-23 15:25:45,241 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 15:25:45,242 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 15:25:45,257 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-11-23 15:25:45,454 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,SelfDestructingSolverStorable13 [2023-11-23 15:25:45,455 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 15:25:45,455 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 15:25:45,455 INFO L85 PathProgramCache]: Analyzing trace with hash -2118052654, now seen corresponding path program 3 times [2023-11-23 15:25:45,455 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 15:25:45,455 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [339638793] [2023-11-23 15:25:45,455 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 15:25:45,456 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 15:25:45,468 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 15:25:45,468 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2058061031] [2023-11-23 15:25:45,468 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-23 15:25:45,469 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 15:25:45,469 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 15:25:45,489 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-11-23 15:25:45,550 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-11-23 15:25:45,683 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2023-11-23 15:25:45,683 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-23 15:25:45,685 INFO L262 TraceCheckSpWp]: Trace formula consists of 262 conjuncts, 43 conjunts are in the unsatisfiable core [2023-11-23 15:25:45,687 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 15:25:45,699 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-11-23 15:25:45,706 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-11-23 15:25:46,064 INFO L134 CoverageAnalysis]: Checked inductivity of 65 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 57 trivial. 0 not checked. [2023-11-23 15:25:46,064 INFO L327 TraceCheckSpWp]: Computing backward predicates... Killed by 15