./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/recursified_nla-digbench/recursified_prodbin-ll.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 023d838f Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/recursified_nla-digbench/recursified_prodbin-ll.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 5ace794fa35bd3dd49302fe61957917bbb7565f1b1f34293812fc47531868d51 --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.fs.icfgbuilder-eval-023d838-m [2024-11-09 23:28:02,582 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-09 23:28:02,666 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-09 23:28:02,670 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-09 23:28:02,671 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-09 23:28:02,703 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-09 23:28:02,705 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-09 23:28:02,706 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-09 23:28:02,707 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-09 23:28:02,708 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-09 23:28:02,708 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-09 23:28:02,709 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-09 23:28:02,709 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-09 23:28:02,710 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-09 23:28:02,710 INFO L153 SettingsManager]: * Use SBE=true [2024-11-09 23:28:02,711 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-09 23:28:02,711 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-09 23:28:02,711 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-09 23:28:02,712 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-09 23:28:02,712 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-09 23:28:02,712 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-09 23:28:02,713 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-09 23:28:02,713 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-09 23:28:02,714 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-09 23:28:02,714 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-09 23:28:02,714 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-09 23:28:02,715 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-09 23:28:02,715 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-09 23:28:02,723 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2024-11-09 23:28:02,723 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-09 23:28:02,724 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-09 23:28:02,724 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-09 23:28:02,724 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-09 23:28:02,724 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-09 23:28:02,725 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-09 23:28:02,725 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-09 23:28:02,725 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-09 23:28:02,725 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-09 23:28:02,725 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-09 23:28:02,725 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-09 23:28:02,726 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-09 23:28:02,726 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-09 23:28:02,726 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 -> 5ace794fa35bd3dd49302fe61957917bbb7565f1b1f34293812fc47531868d51 [2024-11-09 23:28:02,972 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-09 23:28:03,000 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-09 23:28:03,003 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-09 23:28:03,004 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-09 23:28:03,004 INFO L274 PluginConnector]: CDTParser initialized [2024-11-09 23:28:03,005 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursified_nla-digbench/recursified_prodbin-ll.c [2024-11-09 23:28:04,433 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-09 23:28:04,623 INFO L384 CDTParser]: Found 1 translation units. [2024-11-09 23:28:04,623 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_prodbin-ll.c [2024-11-09 23:28:04,630 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/19b694b76/94ed5306acbf4b16a9368b874ec0143c/FLAG5a882f99a [2024-11-09 23:28:04,642 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/19b694b76/94ed5306acbf4b16a9368b874ec0143c [2024-11-09 23:28:04,644 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-09 23:28:04,645 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-09 23:28:04,647 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-09 23:28:04,647 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-09 23:28:04,652 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-09 23:28:04,654 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 11:28:04" (1/1) ... [2024-11-09 23:28:04,655 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@38539723 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 11:28:04, skipping insertion in model container [2024-11-09 23:28:04,655 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 11:28:04" (1/1) ... [2024-11-09 23:28:04,677 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-09 23:28:04,856 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_prodbin-ll.c[1073,1086] [2024-11-09 23:28:04,879 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 23:28:04,889 INFO L200 MainTranslator]: Completed pre-run [2024-11-09 23:28:04,901 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_prodbin-ll.c[1073,1086] [2024-11-09 23:28:04,910 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 23:28:04,925 INFO L204 MainTranslator]: Completed translation [2024-11-09 23:28:04,925 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 11:28:04 WrapperNode [2024-11-09 23:28:04,925 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-09 23:28:04,926 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-09 23:28:04,926 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-09 23:28:04,926 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-09 23:28:04,932 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 11:28:04" (1/1) ... [2024-11-09 23:28:04,938 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 11:28:04" (1/1) ... [2024-11-09 23:28:04,953 INFO L138 Inliner]: procedures = 16, calls = 54, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 65 [2024-11-09 23:28:04,953 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-09 23:28:04,954 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-09 23:28:04,954 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-09 23:28:04,954 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-09 23:28:04,963 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 11:28:04" (1/1) ... [2024-11-09 23:28:04,963 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 11:28:04" (1/1) ... [2024-11-09 23:28:04,965 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 11:28:04" (1/1) ... [2024-11-09 23:28:04,981 INFO L175 MemorySlicer]: Split 29 memory accesses to 6 slices as follows [2, 5, 4, 5, 5, 8]. 28 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2, 0, 0, 0, 0, 0]. The 9 writes are split as follows [0, 1, 1, 2, 2, 3]. [2024-11-09 23:28:04,982 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 11:28:04" (1/1) ... [2024-11-09 23:28:04,982 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 11:28:04" (1/1) ... [2024-11-09 23:28:04,988 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 11:28:04" (1/1) ... [2024-11-09 23:28:04,988 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 11:28:04" (1/1) ... [2024-11-09 23:28:04,990 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 11:28:04" (1/1) ... [2024-11-09 23:28:04,991 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 11:28:04" (1/1) ... [2024-11-09 23:28:04,993 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-09 23:28:04,994 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2024-11-09 23:28:04,994 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2024-11-09 23:28:04,994 INFO L274 PluginConnector]: IcfgBuilder initialized [2024-11-09 23:28:04,995 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 11:28:04" (1/1) ... [2024-11-09 23:28:05,001 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-09 23:28:05,013 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 23:28:05,039 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-09 23:28:05,043 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-09 23:28:05,093 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-09 23:28:05,093 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-09 23:28:05,094 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-11-09 23:28:05,094 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2024-11-09 23:28:05,094 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2024-11-09 23:28:05,094 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#4 [2024-11-09 23:28:05,094 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#5 [2024-11-09 23:28:05,096 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-11-09 23:28:05,096 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2024-11-09 23:28:05,096 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2024-11-09 23:28:05,096 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2024-11-09 23:28:05,096 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2024-11-09 23:28:05,097 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#4 [2024-11-09 23:28:05,097 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#5 [2024-11-09 23:28:05,097 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_0_to_40_0 [2024-11-09 23:28:05,097 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_0_to_40_0 [2024-11-09 23:28:05,098 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-09 23:28:05,098 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-09 23:28:05,098 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2024-11-09 23:28:05,098 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2024-11-09 23:28:05,098 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2024-11-09 23:28:05,099 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2024-11-09 23:28:05,099 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#4 [2024-11-09 23:28:05,099 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#5 [2024-11-09 23:28:05,099 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-09 23:28:05,099 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-09 23:28:05,099 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-09 23:28:05,212 INFO L256 CfgBuilder]: Building ICFG [2024-11-09 23:28:05,214 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-09 23:28:05,378 INFO L1247 $ProcedureCfgBuilder]: dead code at ProgramPoint L82: call ULTIMATE.dealloc(main_~#a~0#1.base, main_~#a~0#1.offset);havoc main_~#a~0#1.base, main_~#a~0#1.offset;call ULTIMATE.dealloc(main_~#b~0#1.base, main_~#b~0#1.offset);havoc main_~#b~0#1.base, main_~#b~0#1.offset;call ULTIMATE.dealloc(main_~#x~0#1.base, main_~#x~0#1.offset);havoc main_~#x~0#1.base, main_~#x~0#1.offset;call ULTIMATE.dealloc(main_~#y~0#1.base, main_~#y~0#1.offset);havoc main_~#y~0#1.base, main_~#y~0#1.offset;call ULTIMATE.dealloc(main_~#z~0#1.base, main_~#z~0#1.offset);havoc main_~#z~0#1.base, main_~#z~0#1.offset; [2024-11-09 23:28:05,407 INFO L? ?]: Removed 10 outVars from TransFormulas that were not future-live. [2024-11-09 23:28:05,407 INFO L307 CfgBuilder]: Performing block encoding [2024-11-09 23:28:05,425 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-09 23:28:05,426 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-09 23:28:05,426 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 09.11 11:28:05 BoogieIcfgContainer [2024-11-09 23:28:05,427 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2024-11-09 23:28:05,430 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-09 23:28:05,430 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-09 23:28:05,433 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-09 23:28:05,433 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 09.11 11:28:04" (1/3) ... [2024-11-09 23:28:05,434 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6799368d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 11:28:05, skipping insertion in model container [2024-11-09 23:28:05,434 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 11:28:04" (2/3) ... [2024-11-09 23:28:05,435 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6799368d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 11:28:05, skipping insertion in model container [2024-11-09 23:28:05,435 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 09.11 11:28:05" (3/3) ... [2024-11-09 23:28:05,436 INFO L112 eAbstractionObserver]: Analyzing ICFG recursified_prodbin-ll.c [2024-11-09 23:28:05,450 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-09 23:28:05,451 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-09 23:28:05,507 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-09 23:28:05,516 INFO L333 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopHeads, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@762e2d9b, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-09 23:28:05,517 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-09 23:28:05,520 INFO L276 IsEmpty]: Start isEmpty. Operand has 28 states, 20 states have (on average 1.3) internal successors, (26), 22 states have internal predecessors, (26), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-09 23:28:05,526 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2024-11-09 23:28:05,526 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 23:28:05,526 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 23:28:05,527 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 23:28:05,531 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 23:28:05,532 INFO L85 PathProgramCache]: Analyzing trace with hash -1790029574, now seen corresponding path program 1 times [2024-11-09 23:28:05,539 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 23:28:05,540 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1967008462] [2024-11-09 23:28:05,540 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 23:28:05,540 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 23:28:05,658 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:28:05,738 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 23:28:05,739 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 23:28:05,739 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1967008462] [2024-11-09 23:28:05,740 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1967008462] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 23:28:05,740 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 23:28:05,741 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-09 23:28:05,742 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1726461733] [2024-11-09 23:28:05,743 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 23:28:05,747 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-09 23:28:05,747 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 23:28:05,770 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-09 23:28:05,770 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-09 23:28:05,772 INFO L87 Difference]: Start difference. First operand has 28 states, 20 states have (on average 1.3) internal successors, (26), 22 states have internal predecessors, (26), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Second operand has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 1 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 23:28:05,792 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 23:28:05,793 INFO L93 Difference]: Finished difference Result 53 states and 68 transitions. [2024-11-09 23:28:05,794 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-09 23:28:05,795 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 1 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 12 [2024-11-09 23:28:05,795 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 23:28:05,801 INFO L225 Difference]: With dead ends: 53 [2024-11-09 23:28:05,801 INFO L226 Difference]: Without dead ends: 24 [2024-11-09 23:28:05,803 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-09 23:28:05,807 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 31 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-09 23:28:05,808 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 23:28:05,825 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2024-11-09 23:28:05,847 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2024-11-09 23:28:05,850 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 17 states have (on average 1.1764705882352942) internal successors, (20), 19 states have internal predecessors, (20), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-09 23:28:05,851 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 27 transitions. [2024-11-09 23:28:05,854 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 27 transitions. Word has length 12 [2024-11-09 23:28:05,854 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 23:28:05,854 INFO L471 AbstractCegarLoop]: Abstraction has 24 states and 27 transitions. [2024-11-09 23:28:05,855 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 1 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 23:28:05,855 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 27 transitions. [2024-11-09 23:28:05,856 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2024-11-09 23:28:05,856 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 23:28:05,857 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 23:28:05,857 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-09 23:28:05,857 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 23:28:05,858 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 23:28:05,858 INFO L85 PathProgramCache]: Analyzing trace with hash -1986543079, now seen corresponding path program 1 times [2024-11-09 23:28:05,858 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 23:28:05,859 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [322862050] [2024-11-09 23:28:05,859 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 23:28:05,860 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 23:28:05,941 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 23:28:05,946 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [400400323] [2024-11-09 23:28:05,946 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 23:28:05,947 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 23:28:05,947 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 23:28:05,949 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 23:28:05,951 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-09 23:28:06,070 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:28:06,074 INFO L255 TraceCheckSpWp]: Trace formula consists of 170 conjuncts, 75 conjuncts are in the unsatisfiable core [2024-11-09 23:28:06,086 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 23:28:06,152 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 [2024-11-09 23:28:06,157 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 [2024-11-09 23:28:06,173 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 [2024-11-09 23:28:06,183 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 [2024-11-09 23:28:06,214 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 [2024-11-09 23:28:06,419 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 [2024-11-09 23:28:06,427 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 [2024-11-09 23:28:06,438 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 [2024-11-09 23:28:06,449 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 [2024-11-09 23:28:06,527 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 23:28:06,527 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 23:28:06,528 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 23:28:06,528 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [322862050] [2024-11-09 23:28:06,528 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 23:28:06,529 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [400400323] [2024-11-09 23:28:06,529 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [400400323] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 23:28:06,529 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 23:28:06,530 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2024-11-09 23:28:06,530 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1517749335] [2024-11-09 23:28:06,531 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 23:28:06,531 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-09 23:28:06,531 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 23:28:06,532 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-09 23:28:06,533 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2024-11-09 23:28:06,533 INFO L87 Difference]: Start difference. First operand 24 states and 27 transitions. Second operand has 8 states, 6 states have (on average 1.6666666666666667) internal successors, (10), 6 states have internal predecessors, (10), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 23:28:06,769 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 23:28:06,769 INFO L93 Difference]: Finished difference Result 41 states and 46 transitions. [2024-11-09 23:28:06,770 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-09 23:28:06,770 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 1.6666666666666667) internal successors, (10), 6 states have internal predecessors, (10), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 12 [2024-11-09 23:28:06,771 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 23:28:06,771 INFO L225 Difference]: With dead ends: 41 [2024-11-09 23:28:06,772 INFO L226 Difference]: Without dead ends: 38 [2024-11-09 23:28:06,772 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2024-11-09 23:28:06,773 INFO L432 NwaCegarLoop]: 17 mSDtfsCounter, 16 mSDsluCounter, 87 mSDsCounter, 0 mSdLazyCounter, 90 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 104 SdHoareTripleChecker+Invalid, 94 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 90 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 23:28:06,774 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 104 Invalid, 94 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 90 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 23:28:06,775 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 38 states. [2024-11-09 23:28:06,785 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 38 to 35. [2024-11-09 23:28:06,786 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 25 states have (on average 1.16) internal successors, (29), 27 states have internal predecessors, (29), 5 states have call successors, (5), 4 states have call predecessors, (5), 4 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2024-11-09 23:28:06,789 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 39 transitions. [2024-11-09 23:28:06,790 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 39 transitions. Word has length 12 [2024-11-09 23:28:06,790 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 23:28:06,790 INFO L471 AbstractCegarLoop]: Abstraction has 35 states and 39 transitions. [2024-11-09 23:28:06,790 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 1.6666666666666667) internal successors, (10), 6 states have internal predecessors, (10), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 23:28:06,791 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 39 transitions. [2024-11-09 23:28:06,791 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2024-11-09 23:28:06,792 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 23:28:06,792 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 23:28:06,807 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2024-11-09 23:28:06,996 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 23:28:06,997 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 23:28:06,997 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 23:28:06,998 INFO L85 PathProgramCache]: Analyzing trace with hash 1165600104, now seen corresponding path program 1 times [2024-11-09 23:28:06,998 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 23:28:06,998 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1826868316] [2024-11-09 23:28:06,998 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 23:28:06,998 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 23:28:07,067 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:28:07,416 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-09 23:28:07,422 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:28:07,515 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:28:07,518 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:28:07,527 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 23:28:07,528 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 23:28:07,528 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1826868316] [2024-11-09 23:28:07,529 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1826868316] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 23:28:07,529 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 23:28:07,529 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2024-11-09 23:28:07,530 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [235098034] [2024-11-09 23:28:07,530 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 23:28:07,530 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-09 23:28:07,530 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 23:28:07,531 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-09 23:28:07,532 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=56, Unknown=0, NotChecked=0, Total=72 [2024-11-09 23:28:07,532 INFO L87 Difference]: Start difference. First operand 35 states and 39 transitions. Second operand has 9 states, 8 states have (on average 2.125) internal successors, (17), 8 states have internal predecessors, (17), 3 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-09 23:28:07,729 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 23:28:07,730 INFO L93 Difference]: Finished difference Result 47 states and 50 transitions. [2024-11-09 23:28:07,730 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-09 23:28:07,730 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.125) internal successors, (17), 8 states have internal predecessors, (17), 3 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 22 [2024-11-09 23:28:07,731 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 23:28:07,732 INFO L225 Difference]: With dead ends: 47 [2024-11-09 23:28:07,733 INFO L226 Difference]: Without dead ends: 36 [2024-11-09 23:28:07,733 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 15 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=37, Invalid=119, Unknown=0, NotChecked=0, Total=156 [2024-11-09 23:28:07,734 INFO L432 NwaCegarLoop]: 11 mSDtfsCounter, 19 mSDsluCounter, 42 mSDsCounter, 0 mSdLazyCounter, 137 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 53 SdHoareTripleChecker+Invalid, 142 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 137 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 23:28:07,737 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 53 Invalid, 142 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 137 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 23:28:07,738 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2024-11-09 23:28:07,745 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 35. [2024-11-09 23:28:07,746 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 25 states have (on average 1.12) internal successors, (28), 26 states have internal predecessors, (28), 5 states have call successors, (5), 4 states have call predecessors, (5), 4 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2024-11-09 23:28:07,749 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 38 transitions. [2024-11-09 23:28:07,750 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 38 transitions. Word has length 22 [2024-11-09 23:28:07,750 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 23:28:07,751 INFO L471 AbstractCegarLoop]: Abstraction has 35 states and 38 transitions. [2024-11-09 23:28:07,751 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 2.125) internal successors, (17), 8 states have internal predecessors, (17), 3 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-09 23:28:07,751 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 38 transitions. [2024-11-09 23:28:07,752 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2024-11-09 23:28:07,752 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 23:28:07,753 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 23:28:07,753 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-11-09 23:28:07,753 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 23:28:07,753 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 23:28:07,753 INFO L85 PathProgramCache]: Analyzing trace with hash -550432642, now seen corresponding path program 1 times [2024-11-09 23:28:07,754 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 23:28:07,754 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [900775640] [2024-11-09 23:28:07,754 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 23:28:07,754 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 23:28:07,861 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 23:28:07,870 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [351013150] [2024-11-09 23:28:07,870 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 23:28:07,870 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 23:28:07,870 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 23:28:07,872 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 23:28:07,886 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-09 23:28:07,990 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:28:07,996 WARN L253 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 139 conjuncts are in the unsatisfiable core [2024-11-09 23:28:08,002 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 23:28:08,007 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 [2024-11-09 23:28:08,010 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 [2024-11-09 23:28:08,016 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 [2024-11-09 23:28:08,022 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 [2024-11-09 23:28:08,029 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 [2024-11-09 23:28:08,304 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 23 treesize of output 15 [2024-11-09 23:28:08,315 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 53 treesize of output 29 [2024-11-09 23:28:08,406 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 40 treesize of output 24 [2024-11-09 23:28:08,420 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 100 treesize of output 57 [2024-11-09 23:28:08,612 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 39 treesize of output 23 [2024-11-09 23:28:08,622 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 [2024-11-09 23:28:08,633 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 32 treesize of output 20 [2024-11-09 23:28:08,640 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 13 [2024-11-09 23:28:08,647 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 24 treesize of output 12 [2024-11-09 23:28:10,325 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 23:28:10,326 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 23:28:21,025 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 4 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 23:28:21,026 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 23:28:21,026 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [900775640] [2024-11-09 23:28:21,026 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 23:28:21,026 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [351013150] [2024-11-09 23:28:21,026 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [351013150] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 23:28:21,026 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 23:28:21,026 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 13] total 23 [2024-11-09 23:28:21,026 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [999783009] [2024-11-09 23:28:21,027 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 23:28:21,027 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-11-09 23:28:21,027 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 23:28:21,028 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-09 23:28:21,028 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=77, Invalid=429, Unknown=0, NotChecked=0, Total=506 [2024-11-09 23:28:21,028 INFO L87 Difference]: Start difference. First operand 35 states and 38 transitions. Second operand has 23 states, 19 states have (on average 1.631578947368421) internal successors, (31), 18 states have internal predecessors, (31), 8 states have call successors, (8), 7 states have call predecessors, (8), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-09 23:28:32,468 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 23:28:32,468 INFO L93 Difference]: Finished difference Result 70 states and 82 transitions. [2024-11-09 23:28:32,469 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2024-11-09 23:28:32,469 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 19 states have (on average 1.631578947368421) internal successors, (31), 18 states have internal predecessors, (31), 8 states have call successors, (8), 7 states have call predecessors, (8), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 24 [2024-11-09 23:28:32,469 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 23:28:32,471 INFO L225 Difference]: With dead ends: 70 [2024-11-09 23:28:32,471 INFO L226 Difference]: Without dead ends: 67 [2024-11-09 23:28:32,472 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 60 GetRequests, 22 SyntacticMatches, 3 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 204 ImplicationChecksByTransitivity, 16.5s TimeCoverageRelationStatistics Valid=214, Invalid=1118, Unknown=0, NotChecked=0, Total=1332 [2024-11-09 23:28:32,473 INFO L432 NwaCegarLoop]: 16 mSDtfsCounter, 58 mSDsluCounter, 179 mSDsCounter, 0 mSdLazyCounter, 378 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 58 SdHoareTripleChecker+Valid, 195 SdHoareTripleChecker+Invalid, 395 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 378 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.3s IncrementalHoareTripleChecker+Time [2024-11-09 23:28:32,473 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [58 Valid, 195 Invalid, 395 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 378 Invalid, 0 Unknown, 0 Unchecked, 4.3s Time] [2024-11-09 23:28:32,473 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2024-11-09 23:28:32,491 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 63. [2024-11-09 23:28:32,492 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 44 states have (on average 1.1590909090909092) internal successors, (51), 47 states have internal predecessors, (51), 9 states have call successors, (9), 7 states have call predecessors, (9), 9 states have return successors, (14), 8 states have call predecessors, (14), 8 states have call successors, (14) [2024-11-09 23:28:32,493 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 74 transitions. [2024-11-09 23:28:32,493 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 74 transitions. Word has length 24 [2024-11-09 23:28:32,495 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 23:28:32,498 INFO L471 AbstractCegarLoop]: Abstraction has 63 states and 74 transitions. [2024-11-09 23:28:32,499 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 19 states have (on average 1.631578947368421) internal successors, (31), 18 states have internal predecessors, (31), 8 states have call successors, (8), 7 states have call predecessors, (8), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-09 23:28:32,499 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 74 transitions. [2024-11-09 23:28:32,499 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2024-11-09 23:28:32,500 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 23:28:32,500 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 23:28:32,518 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-09 23:28:32,700 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable3 [2024-11-09 23:28:32,701 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 23:28:32,701 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 23:28:32,701 INFO L85 PathProgramCache]: Analyzing trace with hash -746946147, now seen corresponding path program 1 times [2024-11-09 23:28:32,701 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 23:28:32,701 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1451582728] [2024-11-09 23:28:32,701 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 23:28:32,702 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 23:28:32,748 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 23:28:32,749 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [163273746] [2024-11-09 23:28:32,751 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 23:28:32,751 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 23:28:32,751 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 23:28:32,753 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 23:28:32,754 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-09 23:28:32,858 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:28:32,866 WARN L253 TraceCheckSpWp]: Trace formula consists of 249 conjuncts, 145 conjuncts are in the unsatisfiable core [2024-11-09 23:28:32,874 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 23:28:32,896 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 [2024-11-09 23:28:32,902 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 [2024-11-09 23:28:32,929 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 [2024-11-09 23:28:32,936 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 [2024-11-09 23:28:32,943 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 [2024-11-09 23:28:33,358 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 106 treesize of output 59 [2024-11-09 23:28:33,369 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 29 treesize of output 17 [2024-11-09 23:28:33,490 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 [2024-11-09 23:28:33,495 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 34 treesize of output 18 [2024-11-09 23:28:33,506 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 [2024-11-09 23:28:33,510 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 [2024-11-09 23:28:33,615 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 23:28:33,615 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 23:28:35,085 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 23:28:35,086 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 23:28:35,086 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1451582728] [2024-11-09 23:28:35,086 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 23:28:35,086 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [163273746] [2024-11-09 23:28:35,086 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [163273746] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 23:28:35,086 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 23:28:35,087 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 14] total 27 [2024-11-09 23:28:35,087 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [538596191] [2024-11-09 23:28:35,087 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 23:28:35,087 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2024-11-09 23:28:35,088 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 23:28:35,088 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2024-11-09 23:28:35,089 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=86, Invalid=616, Unknown=0, NotChecked=0, Total=702 [2024-11-09 23:28:35,089 INFO L87 Difference]: Start difference. First operand 63 states and 74 transitions. Second operand has 27 states, 23 states have (on average 1.434782608695652) internal successors, (33), 21 states have internal predecessors, (33), 8 states have call successors, (8), 7 states have call predecessors, (8), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-09 23:28:44,065 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 23:28:44,065 INFO L93 Difference]: Finished difference Result 115 states and 137 transitions. [2024-11-09 23:28:44,066 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2024-11-09 23:28:44,066 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 23 states have (on average 1.434782608695652) internal successors, (33), 21 states have internal predecessors, (33), 8 states have call successors, (8), 7 states have call predecessors, (8), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 24 [2024-11-09 23:28:44,066 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 23:28:44,067 INFO L225 Difference]: With dead ends: 115 [2024-11-09 23:28:44,067 INFO L226 Difference]: Without dead ends: 112 [2024-11-09 23:28:44,068 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 66 GetRequests, 18 SyntacticMatches, 3 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 422 ImplicationChecksByTransitivity, 8.9s TimeCoverageRelationStatistics Valid=312, Invalid=1849, Unknown=1, NotChecked=0, Total=2162 [2024-11-09 23:28:44,069 INFO L432 NwaCegarLoop]: 16 mSDtfsCounter, 61 mSDsluCounter, 146 mSDsCounter, 0 mSdLazyCounter, 393 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 61 SdHoareTripleChecker+Valid, 162 SdHoareTripleChecker+Invalid, 419 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 393 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.2s IncrementalHoareTripleChecker+Time [2024-11-09 23:28:44,069 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [61 Valid, 162 Invalid, 419 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 393 Invalid, 0 Unknown, 0 Unchecked, 1.2s Time] [2024-11-09 23:28:44,070 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 112 states. [2024-11-09 23:28:44,090 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 112 to 104. [2024-11-09 23:28:44,091 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 104 states, 72 states have (on average 1.1666666666666667) internal successors, (84), 78 states have internal predecessors, (84), 15 states have call successors, (15), 12 states have call predecessors, (15), 16 states have return successors, (25), 13 states have call predecessors, (25), 14 states have call successors, (25) [2024-11-09 23:28:44,092 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 104 states to 104 states and 124 transitions. [2024-11-09 23:28:44,092 INFO L78 Accepts]: Start accepts. Automaton has 104 states and 124 transitions. Word has length 24 [2024-11-09 23:28:44,093 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 23:28:44,093 INFO L471 AbstractCegarLoop]: Abstraction has 104 states and 124 transitions. [2024-11-09 23:28:44,093 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 23 states have (on average 1.434782608695652) internal successors, (33), 21 states have internal predecessors, (33), 8 states have call successors, (8), 7 states have call predecessors, (8), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-09 23:28:44,093 INFO L276 IsEmpty]: Start isEmpty. Operand 104 states and 124 transitions. [2024-11-09 23:28:44,094 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2024-11-09 23:28:44,094 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 23:28:44,094 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 23:28:44,110 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-11-09 23:28:44,298 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 23:28:44,299 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 23:28:44,299 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 23:28:44,299 INFO L85 PathProgramCache]: Analyzing trace with hash -1858051966, now seen corresponding path program 1 times [2024-11-09 23:28:44,299 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 23:28:44,300 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [187125604] [2024-11-09 23:28:44,300 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 23:28:44,300 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 23:28:44,342 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 23:28:44,344 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [440970980] [2024-11-09 23:28:44,344 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 23:28:44,344 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 23:28:44,344 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 23:28:44,346 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 23:28:44,347 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-09 23:28:44,784 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:28:44,788 WARN L253 TraceCheckSpWp]: Trace formula consists of 337 conjuncts, 222 conjuncts are in the unsatisfiable core [2024-11-09 23:28:44,794 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 23:28:44,798 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 [2024-11-09 23:28:44,800 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 [2024-11-09 23:28:44,805 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 [2024-11-09 23:28:44,811 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 [2024-11-09 23:28:44,817 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 [2024-11-09 23:28:45,109 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 23 treesize of output 15 [2024-11-09 23:28:45,115 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 53 treesize of output 29 [2024-11-09 23:28:45,169 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 98 treesize of output 55 [2024-11-09 23:28:45,186 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 40 treesize of output 24 [2024-11-09 23:28:46,049 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 31 treesize of output 19 [2024-11-09 23:28:46,060 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 118 treesize of output 67 [2024-11-09 23:28:46,335 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 [2024-11-09 23:28:46,340 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 28 treesize of output 16 [2024-11-09 23:28:46,345 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 [2024-11-09 23:28:46,356 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 65 treesize of output 41 [2024-11-09 23:28:46,366 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 [2024-11-09 23:28:48,135 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 0 proven. 22 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 23:28:48,136 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 23:29:07,770 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 23:29:07,770 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [187125604] [2024-11-09 23:29:07,770 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 23:29:07,770 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [440970980] [2024-11-09 23:29:07,770 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [440970980] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 23:29:07,770 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-09 23:29:07,770 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [26] total 26 [2024-11-09 23:29:07,770 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [920398068] [2024-11-09 23:29:07,771 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-09 23:29:07,771 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2024-11-09 23:29:07,771 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 23:29:07,771 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2024-11-09 23:29:07,772 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=134, Invalid=985, Unknown=3, NotChecked=0, Total=1122 [2024-11-09 23:29:07,773 INFO L87 Difference]: Start difference. First operand 104 states and 124 transitions. Second operand has 26 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 20 states have internal predecessors, (28), 6 states have call successors, (6), 6 states have call predecessors, (6), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-09 23:29:09,984 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 23:29:09,987 INFO L93 Difference]: Finished difference Result 136 states and 159 transitions. [2024-11-09 23:29:09,989 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2024-11-09 23:29:09,990 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 20 states have internal predecessors, (28), 6 states have call successors, (6), 6 states have call predecessors, (6), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 36 [2024-11-09 23:29:09,990 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 23:29:09,992 INFO L225 Difference]: With dead ends: 136 [2024-11-09 23:29:09,993 INFO L226 Difference]: Without dead ends: 131 [2024-11-09 23:29:09,994 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 60 GetRequests, 12 SyntacticMatches, 4 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 465 ImplicationChecksByTransitivity, 21.2s TimeCoverageRelationStatistics Valid=254, Invalid=1813, Unknown=3, NotChecked=0, Total=2070 [2024-11-09 23:29:09,996 INFO L432 NwaCegarLoop]: 22 mSDtfsCounter, 38 mSDsluCounter, 198 mSDsCounter, 0 mSdLazyCounter, 618 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 38 SdHoareTripleChecker+Valid, 220 SdHoareTripleChecker+Invalid, 628 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 618 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.2s IncrementalHoareTripleChecker+Time [2024-11-09 23:29:09,997 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [38 Valid, 220 Invalid, 628 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 618 Invalid, 0 Unknown, 0 Unchecked, 1.2s Time] [2024-11-09 23:29:09,998 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 131 states. [2024-11-09 23:29:10,032 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 131 to 126. [2024-11-09 23:29:10,033 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 126 states, 87 states have (on average 1.160919540229885) internal successors, (101), 93 states have internal predecessors, (101), 18 states have call successors, (18), 15 states have call predecessors, (18), 20 states have return successors, (30), 17 states have call predecessors, (30), 16 states have call successors, (30) [2024-11-09 23:29:10,034 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 126 states to 126 states and 149 transitions. [2024-11-09 23:29:10,034 INFO L78 Accepts]: Start accepts. Automaton has 126 states and 149 transitions. Word has length 36 [2024-11-09 23:29:10,035 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 23:29:10,035 INFO L471 AbstractCegarLoop]: Abstraction has 126 states and 149 transitions. [2024-11-09 23:29:10,035 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 20 states have internal predecessors, (28), 6 states have call successors, (6), 6 states have call predecessors, (6), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-09 23:29:10,035 INFO L276 IsEmpty]: Start isEmpty. Operand 126 states and 149 transitions. [2024-11-09 23:29:10,038 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2024-11-09 23:29:10,038 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 23:29:10,039 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 23:29:10,048 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-11-09 23:29:10,239 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 23:29:10,239 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 23:29:10,240 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 23:29:10,240 INFO L85 PathProgramCache]: Analyzing trace with hash 595372546, now seen corresponding path program 2 times [2024-11-09 23:29:10,240 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 23:29:10,240 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1004187243] [2024-11-09 23:29:10,240 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 23:29:10,240 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 23:29:10,298 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 23:29:10,301 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [522807674] [2024-11-09 23:29:10,302 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-09 23:29:10,302 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 23:29:10,302 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 23:29:10,304 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 23:29:10,305 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-09 23:29:10,457 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-09 23:29:10,457 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 23:29:10,461 WARN L253 TraceCheckSpWp]: Trace formula consists of 337 conjuncts, 209 conjuncts are in the unsatisfiable core [2024-11-09 23:29:10,466 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 23:29:10,474 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 [2024-11-09 23:29:10,482 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 [2024-11-09 23:29:10,496 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 [2024-11-09 23:29:10,501 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 [2024-11-09 23:29:10,506 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 [2024-11-09 23:29:10,798 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 29 treesize of output 17 [2024-11-09 23:29:10,805 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 106 treesize of output 59 [2024-11-09 23:29:11,186 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 23 treesize of output 15 [2024-11-09 23:29:11,196 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 47 treesize of output 27 [2024-11-09 23:29:11,279 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 42 treesize of output 26 [2024-11-09 23:29:11,292 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 111 treesize of output 64 [2024-11-09 23:29:11,437 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 53 treesize of output 33 [2024-11-09 23:29:11,444 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 [2024-11-09 23:29:11,457 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 [2024-11-09 23:29:11,464 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 [2024-11-09 23:29:11,470 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 [2024-11-09 23:29:11,595 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 0 proven. 22 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 23:29:11,595 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 23:29:35,417 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 23:29:35,418 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1004187243] [2024-11-09 23:29:35,418 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 23:29:35,418 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [522807674] [2024-11-09 23:29:35,418 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [522807674] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 23:29:35,418 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-09 23:29:35,418 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2024-11-09 23:29:35,418 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1631392999] [2024-11-09 23:29:35,418 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-09 23:29:35,419 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-09 23:29:35,419 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 23:29:35,419 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-09 23:29:35,420 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=140, Invalid=982, Unknown=0, NotChecked=0, Total=1122 [2024-11-09 23:29:35,420 INFO L87 Difference]: Start difference. First operand 126 states and 149 transitions. Second operand has 21 states, 19 states have (on average 1.4736842105263157) internal successors, (28), 17 states have internal predecessors, (28), 5 states have call successors, (6), 6 states have call predecessors, (6), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-09 23:29:38,493 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 23:29:38,493 INFO L93 Difference]: Finished difference Result 156 states and 181 transitions. [2024-11-09 23:29:38,494 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2024-11-09 23:29:38,494 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 19 states have (on average 1.4736842105263157) internal successors, (28), 17 states have internal predecessors, (28), 5 states have call successors, (6), 6 states have call predecessors, (6), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 36 [2024-11-09 23:29:38,494 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 23:29:38,495 INFO L225 Difference]: With dead ends: 156 [2024-11-09 23:29:38,495 INFO L226 Difference]: Without dead ends: 143 [2024-11-09 23:29:38,496 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 26 SyntacticMatches, 2 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 318 ImplicationChecksByTransitivity, 25.6s TimeCoverageRelationStatistics Valid=250, Invalid=1556, Unknown=0, NotChecked=0, Total=1806 [2024-11-09 23:29:38,497 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 28 mSDsluCounter, 267 mSDsCounter, 0 mSdLazyCounter, 518 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 295 SdHoareTripleChecker+Invalid, 526 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 518 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2024-11-09 23:29:38,497 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 295 Invalid, 526 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 518 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2024-11-09 23:29:38,498 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 143 states. [2024-11-09 23:29:38,524 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 143 to 139. [2024-11-09 23:29:38,524 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 139 states, 97 states have (on average 1.1443298969072164) internal successors, (111), 103 states have internal predecessors, (111), 20 states have call successors, (20), 18 states have call predecessors, (20), 21 states have return successors, (31), 17 states have call predecessors, (31), 18 states have call successors, (31) [2024-11-09 23:29:38,526 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 139 states to 139 states and 162 transitions. [2024-11-09 23:29:38,526 INFO L78 Accepts]: Start accepts. Automaton has 139 states and 162 transitions. Word has length 36 [2024-11-09 23:29:38,526 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 23:29:38,527 INFO L471 AbstractCegarLoop]: Abstraction has 139 states and 162 transitions. [2024-11-09 23:29:38,527 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 19 states have (on average 1.4736842105263157) internal successors, (28), 17 states have internal predecessors, (28), 5 states have call successors, (6), 6 states have call predecessors, (6), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-09 23:29:38,527 INFO L276 IsEmpty]: Start isEmpty. Operand 139 states and 162 transitions. [2024-11-09 23:29:38,528 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2024-11-09 23:29:38,528 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 23:29:38,528 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 23:29:38,546 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-09 23:29:38,729 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 23:29:38,729 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 23:29:38,729 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 23:29:38,729 INFO L85 PathProgramCache]: Analyzing trace with hash 729807107, now seen corresponding path program 1 times [2024-11-09 23:29:38,730 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 23:29:38,730 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1747450216] [2024-11-09 23:29:38,730 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 23:29:38,730 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 23:29:38,765 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 23:29:38,767 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2113780629] [2024-11-09 23:29:38,767 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 23:29:38,767 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 23:29:38,767 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 23:29:38,769 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 23:29:38,772 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-09 23:29:38,905 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:29:38,913 INFO L255 TraceCheckSpWp]: Trace formula consists of 281 conjuncts, 93 conjuncts are in the unsatisfiable core [2024-11-09 23:29:38,920 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 23:29:38,925 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 [2024-11-09 23:29:38,932 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 [2024-11-09 23:29:38,942 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 [2024-11-09 23:29:38,958 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-09 23:29:38,961 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-09 23:29:39,434 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 32 treesize of output 20 [2024-11-09 23:29:39,441 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 19 [2024-11-09 23:29:39,444 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 23 treesize of output 15 [2024-11-09 23:29:39,474 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 28 treesize of output 16 [2024-11-09 23:29:39,481 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 [2024-11-09 23:29:39,483 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 [2024-11-09 23:29:39,546 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 4 proven. 7 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-09 23:29:39,546 INFO L311 TraceCheckSpWp]: Computing backward predicates...