/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerCTransformed.xml -s ../../../trunk/examples/settings/loopacceleration/qvasr/qvasr_64.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/dijkstra-u_unwindbound5.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-5d317bd [2022-03-18 23:06:51,337 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-03-18 23:06:51,338 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-03-18 23:06:51,373 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-03-18 23:06:51,373 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-03-18 23:06:51,374 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-03-18 23:06:51,376 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-03-18 23:06:51,378 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-03-18 23:06:51,379 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-03-18 23:06:51,383 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-03-18 23:06:51,383 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-03-18 23:06:51,384 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-03-18 23:06:51,385 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-03-18 23:06:51,386 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-03-18 23:06:51,387 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-03-18 23:06:51,389 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-03-18 23:06:51,390 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-03-18 23:06:51,390 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-03-18 23:06:51,392 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-03-18 23:06:51,396 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-03-18 23:06:51,397 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-03-18 23:06:51,398 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-03-18 23:06:51,399 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-03-18 23:06:51,399 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-03-18 23:06:51,400 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-03-18 23:06:51,405 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-03-18 23:06:51,405 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-03-18 23:06:51,405 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-03-18 23:06:51,406 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-03-18 23:06:51,406 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-03-18 23:06:51,407 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-03-18 23:06:51,407 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-03-18 23:06:51,408 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-03-18 23:06:51,408 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-03-18 23:06:51,409 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-03-18 23:06:51,409 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-03-18 23:06:51,410 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-03-18 23:06:51,410 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-03-18 23:06:51,410 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-03-18 23:06:51,410 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-03-18 23:06:51,411 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-03-18 23:06:51,412 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-03-18 23:06:51,412 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/loopacceleration/qvasr/qvasr_64.epf [2022-03-18 23:06:51,430 INFO L113 SettingsManager]: Loading preferences was successful [2022-03-18 23:06:51,430 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-03-18 23:06:51,431 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-03-18 23:06:51,431 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-03-18 23:06:51,432 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-03-18 23:06:51,432 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-03-18 23:06:51,432 INFO L138 SettingsManager]: * Use SBE=true [2022-03-18 23:06:51,432 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-03-18 23:06:51,432 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-03-18 23:06:51,432 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-03-18 23:06:51,433 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-03-18 23:06:51,433 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-03-18 23:06:51,433 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-03-18 23:06:51,433 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-03-18 23:06:51,433 INFO L138 SettingsManager]: * Use constant arrays=true [2022-03-18 23:06:51,433 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-03-18 23:06:51,433 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-03-18 23:06:51,433 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-03-18 23:06:51,433 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-03-18 23:06:51,433 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-18 23:06:51,433 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-03-18 23:06:51,434 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-03-18 23:06:51,434 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-03-18 23:06:51,434 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-03-18 23:06:51,434 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-03-18 23:06:51,434 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-03-18 23:06:51,434 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2022-03-18 23:06:51,434 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2022-03-18 23:06:51,435 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-03-18 23:06:51,435 INFO L138 SettingsManager]: * TransformationType=LOOP_ACCELERATION_QVASR 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.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-03-18 23:06:51,621 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-03-18 23:06:51,635 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-03-18 23:06:51,637 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-03-18 23:06:51,637 INFO L271 PluginConnector]: Initializing CDTParser... [2022-03-18 23:06:51,638 INFO L275 PluginConnector]: CDTParser initialized [2022-03-18 23:06:51,639 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/dijkstra-u_unwindbound5.c [2022-03-18 23:06:51,691 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/0f30518c7/62cd4ea678814ac3a55e3d42333b3272/FLAGab205a481 [2022-03-18 23:06:52,050 INFO L306 CDTParser]: Found 1 translation units. [2022-03-18 23:06:52,050 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/dijkstra-u_unwindbound5.c [2022-03-18 23:06:52,055 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/0f30518c7/62cd4ea678814ac3a55e3d42333b3272/FLAGab205a481 [2022-03-18 23:06:52,473 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/0f30518c7/62cd4ea678814ac3a55e3d42333b3272 [2022-03-18 23:06:52,475 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-03-18 23:06:52,476 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-03-18 23:06:52,477 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-03-18 23:06:52,477 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-03-18 23:06:52,482 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-03-18 23:06:52,483 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 18.03 11:06:52" (1/1) ... [2022-03-18 23:06:52,484 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7f4f8906 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 11:06:52, skipping insertion in model container [2022-03-18 23:06:52,484 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 18.03 11:06:52" (1/1) ... [2022-03-18 23:06:52,488 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-03-18 23:06:52,503 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-03-18 23:06:52,604 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/dijkstra-u_unwindbound5.c[525,538] [2022-03-18 23:06:52,634 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-18 23:06:52,639 INFO L203 MainTranslator]: Completed pre-run [2022-03-18 23:06:52,646 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/dijkstra-u_unwindbound5.c[525,538] [2022-03-18 23:06:52,656 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-18 23:06:52,664 INFO L208 MainTranslator]: Completed translation [2022-03-18 23:06:52,665 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 11:06:52 WrapperNode [2022-03-18 23:06:52,665 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-03-18 23:06:52,666 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-03-18 23:06:52,666 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-03-18 23:06:52,666 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-03-18 23:06:52,673 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 11:06:52" (1/1) ... [2022-03-18 23:06:52,673 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 11:06:52" (1/1) ... [2022-03-18 23:06:52,677 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 11:06:52" (1/1) ... [2022-03-18 23:06:52,677 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 11:06:52" (1/1) ... [2022-03-18 23:06:52,680 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 11:06:52" (1/1) ... [2022-03-18 23:06:52,683 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 11:06:52" (1/1) ... [2022-03-18 23:06:52,683 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 11:06:52" (1/1) ... [2022-03-18 23:06:52,684 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-03-18 23:06:52,685 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-03-18 23:06:52,685 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-03-18 23:06:52,685 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-03-18 23:06:52,686 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 11:06:52" (1/1) ... [2022-03-18 23:06:52,695 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-18 23:06:52,703 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 23:06:52,716 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-03-18 23:06:52,739 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-03-18 23:06:52,748 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-03-18 23:06:52,748 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-03-18 23:06:52,749 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-03-18 23:06:52,749 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-03-18 23:06:52,749 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-03-18 23:06:52,749 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-03-18 23:06:52,750 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-03-18 23:06:52,750 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-03-18 23:06:52,752 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-03-18 23:06:52,752 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-03-18 23:06:52,752 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_uint [2022-03-18 23:06:52,752 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-03-18 23:06:52,753 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-03-18 23:06:52,753 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-03-18 23:06:52,753 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-03-18 23:06:52,753 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-03-18 23:06:52,755 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-03-18 23:06:52,755 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-03-18 23:06:52,755 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-03-18 23:06:52,755 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-03-18 23:06:52,794 INFO L234 CfgBuilder]: Building ICFG [2022-03-18 23:06:52,795 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-03-18 23:06:52,970 INFO L275 CfgBuilder]: Performing block encoding [2022-03-18 23:06:52,988 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-03-18 23:06:52,988 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-03-18 23:06:52,989 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.03 11:06:52 BoogieIcfgContainer [2022-03-18 23:06:52,989 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-03-18 23:06:52,990 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-03-18 23:06:52,990 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-03-18 23:06:52,992 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-03-18 23:06:52,994 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.03 11:06:52" (1/1) ... [2022-03-18 23:06:53,024 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 18.03 11:06:53 BasicIcfg [2022-03-18 23:06:53,024 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-03-18 23:06:53,025 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-03-18 23:06:53,026 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-03-18 23:06:53,033 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-03-18 23:06:53,033 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 18.03 11:06:52" (1/4) ... [2022-03-18 23:06:53,033 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@165609e3 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.03 11:06:53, skipping insertion in model container [2022-03-18 23:06:53,034 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 11:06:52" (2/4) ... [2022-03-18 23:06:53,034 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@165609e3 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.03 11:06:53, skipping insertion in model container [2022-03-18 23:06:53,034 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.03 11:06:52" (3/4) ... [2022-03-18 23:06:53,034 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@165609e3 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 18.03 11:06:53, skipping insertion in model container [2022-03-18 23:06:53,034 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 18.03 11:06:53" (4/4) ... [2022-03-18 23:06:53,035 INFO L111 eAbstractionObserver]: Analyzing ICFG dijkstra-u_unwindbound5.cqvasr [2022-03-18 23:06:53,038 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-03-18 23:06:53,038 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-03-18 23:06:53,080 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-03-18 23:06:53,086 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, 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 [2022-03-18 23:06:53,087 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-03-18 23:06:53,107 INFO L276 IsEmpty]: Start isEmpty. Operand has 39 states, 21 states have (on average 1.4761904761904763) internal successors, (31), 22 states have internal predecessors, (31), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-03-18 23:06:53,110 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-03-18 23:06:53,111 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 23:06:53,111 INFO L500 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 23:06:53,112 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 23:06:53,115 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 23:06:53,115 INFO L85 PathProgramCache]: Analyzing trace with hash -460462115, now seen corresponding path program 1 times [2022-03-18 23:06:53,120 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 23:06:53,121 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1085529274] [2022-03-18 23:06:53,122 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 23:06:53,122 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 23:06:53,195 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 23:06:53,237 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-18 23:06:53,240 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 23:06:53,248 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-18 23:06:53,249 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 23:06:53,253 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-18 23:06:53,254 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 23:06:53,254 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1085529274] [2022-03-18 23:06:53,254 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1085529274] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-18 23:06:53,255 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-18 23:06:53,255 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-18 23:06:53,256 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1255604540] [2022-03-18 23:06:53,256 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-18 23:06:53,259 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-03-18 23:06:53,259 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 23:06:53,275 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-03-18 23:06:53,276 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-18 23:06:53,277 INFO L87 Difference]: Start difference. First operand has 39 states, 21 states have (on average 1.4761904761904763) internal successors, (31), 22 states have internal predecessors, (31), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-18 23:06:55,399 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-03-18 23:06:55,472 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 23:06:55,473 INFO L93 Difference]: Finished difference Result 70 states and 111 transitions. [2022-03-18 23:06:55,474 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-03-18 23:06:55,475 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2022-03-18 23:06:55,475 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 23:06:55,479 INFO L225 Difference]: With dead ends: 70 [2022-03-18 23:06:55,480 INFO L226 Difference]: Without dead ends: 35 [2022-03-18 23:06:55,481 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-18 23:06:55,483 INFO L912 BasicCegarLoop]: 49 mSDtfsCounter, 10 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 11 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 53 SdHoareTripleChecker+Invalid, 37 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.2s IncrementalHoareTripleChecker+Time [2022-03-18 23:06:55,484 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 53 Invalid, 37 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 25 Invalid, 1 Unknown, 0 Unchecked, 2.2s Time] [2022-03-18 23:06:55,494 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2022-03-18 23:06:55,517 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 34. [2022-03-18 23:06:55,518 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-03-18 23:06:55,522 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 46 transitions. [2022-03-18 23:06:55,523 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 46 transitions. Word has length 18 [2022-03-18 23:06:55,523 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 23:06:55,523 INFO L478 AbstractCegarLoop]: Abstraction has 34 states and 46 transitions. [2022-03-18 23:06:55,524 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-18 23:06:55,524 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 46 transitions. [2022-03-18 23:06:55,525 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2022-03-18 23:06:55,525 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 23:06:55,525 INFO L500 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 23:06:55,526 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-03-18 23:06:55,526 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 23:06:55,527 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 23:06:55,527 INFO L85 PathProgramCache]: Analyzing trace with hash -889932734, now seen corresponding path program 1 times [2022-03-18 23:06:55,527 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 23:06:55,528 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1407998657] [2022-03-18 23:06:55,528 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 23:06:55,528 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 23:06:55,555 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 23:06:55,556 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [763770417] [2022-03-18 23:06:55,556 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 23:06:55,556 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 23:06:55,556 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 23:06:55,567 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) [2022-03-18 23:06:55,568 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-03-18 23:06:55,614 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 23:06:55,616 INFO L263 TraceCheckSpWp]: Trace formula consists of 85 conjuncts, 5 conjunts are in the unsatisfiable core [2022-03-18 23:06:55,621 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 23:06:55,704 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-18 23:06:55,704 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-18 23:06:55,705 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 23:06:55,711 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1407998657] [2022-03-18 23:06:55,712 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 23:06:55,712 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [763770417] [2022-03-18 23:06:55,713 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [763770417] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-18 23:06:55,713 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-18 23:06:55,713 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-03-18 23:06:55,714 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1232130593] [2022-03-18 23:06:55,714 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-18 23:06:55,715 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-03-18 23:06:55,715 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 23:06:55,716 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-03-18 23:06:55,717 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-03-18 23:06:55,719 INFO L87 Difference]: Start difference. First operand 34 states and 46 transitions. Second operand has 4 states, 4 states have (on average 3.5) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-03-18 23:06:55,743 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 23:06:55,747 INFO L93 Difference]: Finished difference Result 55 states and 78 transitions. [2022-03-18 23:06:55,748 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-03-18 23:06:55,748 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 3.5) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 20 [2022-03-18 23:06:55,749 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 23:06:55,750 INFO L225 Difference]: With dead ends: 55 [2022-03-18 23:06:55,750 INFO L226 Difference]: Without dead ends: 36 [2022-03-18 23:06:55,751 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-03-18 23:06:55,752 INFO L912 BasicCegarLoop]: 44 mSDtfsCounter, 0 mSDsluCounter, 75 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 119 SdHoareTripleChecker+Invalid, 8 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 8 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-18 23:06:55,752 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 119 Invalid, 8 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 8 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-18 23:06:55,754 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2022-03-18 23:06:55,762 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 36. [2022-03-18 23:06:55,763 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 20 states have (on average 1.3) internal successors, (26), 21 states have internal predecessors, (26), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-03-18 23:06:55,764 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 48 transitions. [2022-03-18 23:06:55,764 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 48 transitions. Word has length 20 [2022-03-18 23:06:55,765 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 23:06:55,765 INFO L478 AbstractCegarLoop]: Abstraction has 36 states and 48 transitions. [2022-03-18 23:06:55,765 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 3.5) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-03-18 23:06:55,765 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 48 transitions. [2022-03-18 23:06:55,766 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2022-03-18 23:06:55,766 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 23:06:55,766 INFO L500 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 23:06:55,799 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-03-18 23:06:55,975 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 23:06:55,976 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 23:06:55,976 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 23:06:55,976 INFO L85 PathProgramCache]: Analyzing trace with hash 1699853977, now seen corresponding path program 1 times [2022-03-18 23:06:55,976 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 23:06:55,976 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1758104277] [2022-03-18 23:06:55,977 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 23:06:55,977 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 23:06:55,989 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 23:06:55,989 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [835550754] [2022-03-18 23:06:55,989 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 23:06:55,989 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 23:06:55,990 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 23:06:55,992 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) [2022-03-18 23:06:55,993 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-03-18 23:06:56,027 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 23:06:56,028 INFO L263 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-18 23:06:56,032 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 23:06:56,105 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-18 23:06:56,106 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-18 23:06:56,106 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 23:06:56,106 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1758104277] [2022-03-18 23:06:56,106 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 23:06:56,106 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [835550754] [2022-03-18 23:06:56,106 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [835550754] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-18 23:06:56,106 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-18 23:06:56,106 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-18 23:06:56,106 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [467470754] [2022-03-18 23:06:56,106 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-18 23:06:56,107 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-18 23:06:56,107 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 23:06:56,107 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-18 23:06:56,107 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-03-18 23:06:56,108 INFO L87 Difference]: Start difference. First operand 36 states and 48 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-03-18 23:06:56,137 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 23:06:56,137 INFO L93 Difference]: Finished difference Result 49 states and 64 transitions. [2022-03-18 23:06:56,137 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-18 23:06:56,137 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 21 [2022-03-18 23:06:56,138 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 23:06:56,139 INFO L225 Difference]: With dead ends: 49 [2022-03-18 23:06:56,139 INFO L226 Difference]: Without dead ends: 40 [2022-03-18 23:06:56,139 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 20 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-03-18 23:06:56,141 INFO L912 BasicCegarLoop]: 43 mSDtfsCounter, 7 mSDsluCounter, 106 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 149 SdHoareTripleChecker+Invalid, 18 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-18 23:06:56,142 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [7 Valid, 149 Invalid, 18 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-18 23:06:56,143 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2022-03-18 23:06:56,152 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 39. [2022-03-18 23:06:56,152 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 23 states have (on average 1.3043478260869565) internal successors, (30), 24 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-03-18 23:06:56,156 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 52 transitions. [2022-03-18 23:06:56,156 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 52 transitions. Word has length 21 [2022-03-18 23:06:56,156 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 23:06:56,156 INFO L478 AbstractCegarLoop]: Abstraction has 39 states and 52 transitions. [2022-03-18 23:06:56,158 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-03-18 23:06:56,158 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 52 transitions. [2022-03-18 23:06:56,158 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2022-03-18 23:06:56,158 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 23:06:56,158 INFO L500 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 23:06:56,175 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-03-18 23:06:56,359 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2022-03-18 23:06:56,359 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 23:06:56,359 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 23:06:56,360 INFO L85 PathProgramCache]: Analyzing trace with hash 1700986035, now seen corresponding path program 1 times [2022-03-18 23:06:56,360 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 23:06:56,360 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1102815145] [2022-03-18 23:06:56,360 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 23:06:56,360 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 23:06:56,405 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 23:06:56,516 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-18 23:06:56,518 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 23:06:56,521 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-18 23:06:56,521 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 23:06:56,524 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-18 23:06:56,524 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 23:06:56,524 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1102815145] [2022-03-18 23:06:56,524 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1102815145] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-18 23:06:56,524 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-18 23:06:56,524 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-03-18 23:06:56,524 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [89866895] [2022-03-18 23:06:56,525 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-18 23:06:56,525 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-03-18 23:06:56,525 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 23:06:56,525 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-03-18 23:06:56,525 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2022-03-18 23:06:56,525 INFO L87 Difference]: Start difference. First operand 39 states and 52 transitions. Second operand has 7 states, 7 states have (on average 2.142857142857143) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-18 23:06:59,375 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-03-18 23:06:59,413 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 23:06:59,413 INFO L93 Difference]: Finished difference Result 72 states and 104 transitions. [2022-03-18 23:06:59,413 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-03-18 23:06:59,413 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.142857142857143) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 21 [2022-03-18 23:06:59,414 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 23:06:59,414 INFO L225 Difference]: With dead ends: 72 [2022-03-18 23:06:59,414 INFO L226 Difference]: Without dead ends: 51 [2022-03-18 23:06:59,415 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2022-03-18 23:06:59,415 INFO L912 BasicCegarLoop]: 45 mSDtfsCounter, 24 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 166 mSolverCounterSat, 40 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 133 SdHoareTripleChecker+Invalid, 207 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 40 IncrementalHoareTripleChecker+Valid, 166 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.8s IncrementalHoareTripleChecker+Time [2022-03-18 23:06:59,415 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [25 Valid, 133 Invalid, 207 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [40 Valid, 166 Invalid, 1 Unknown, 0 Unchecked, 2.8s Time] [2022-03-18 23:06:59,416 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2022-03-18 23:06:59,422 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2022-03-18 23:06:59,422 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 29 states have internal predecessors, (34), 19 states have call successors, (19), 5 states have call predecessors, (19), 4 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-03-18 23:06:59,423 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 69 transitions. [2022-03-18 23:06:59,423 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 69 transitions. Word has length 21 [2022-03-18 23:06:59,423 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 23:06:59,423 INFO L478 AbstractCegarLoop]: Abstraction has 51 states and 69 transitions. [2022-03-18 23:06:59,423 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.142857142857143) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-18 23:06:59,424 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 69 transitions. [2022-03-18 23:06:59,424 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2022-03-18 23:06:59,424 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 23:06:59,424 INFO L500 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 23:06:59,424 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2022-03-18 23:06:59,424 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 23:06:59,425 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 23:06:59,425 INFO L85 PathProgramCache]: Analyzing trace with hash 1908885951, now seen corresponding path program 1 times [2022-03-18 23:06:59,425 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 23:06:59,425 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [442513094] [2022-03-18 23:06:59,425 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 23:06:59,425 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 23:06:59,452 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 23:06:59,452 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1362851778] [2022-03-18 23:06:59,452 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 23:06:59,452 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 23:06:59,453 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 23:06:59,475 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) [2022-03-18 23:06:59,497 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-03-18 23:06:59,520 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 23:06:59,520 INFO L263 TraceCheckSpWp]: Trace formula consists of 93 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-18 23:06:59,521 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 23:06:59,573 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-18 23:06:59,573 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 23:06:59,630 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-18 23:06:59,630 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 23:06:59,630 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [442513094] [2022-03-18 23:06:59,630 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 23:06:59,630 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1362851778] [2022-03-18 23:06:59,630 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1362851778] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-18 23:06:59,631 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-18 23:06:59,631 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2022-03-18 23:06:59,631 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1804322527] [2022-03-18 23:06:59,631 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-18 23:06:59,631 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-03-18 23:06:59,631 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 23:06:59,631 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-03-18 23:06:59,631 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2022-03-18 23:06:59,632 INFO L87 Difference]: Start difference. First operand 51 states and 69 transitions. Second operand has 8 states, 8 states have (on average 3.625) internal successors, (29), 8 states have internal predecessors, (29), 4 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2022-03-18 23:07:03,062 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-03-18 23:07:06,605 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-03-18 23:07:08,850 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-03-18 23:07:10,936 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 23:07:12,938 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 23:07:12,942 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 23:07:12,942 INFO L93 Difference]: Finished difference Result 104 states and 146 transitions. [2022-03-18 23:07:12,943 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-03-18 23:07:12,943 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.625) internal successors, (29), 8 states have internal predecessors, (29), 4 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) Word has length 23 [2022-03-18 23:07:12,943 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 23:07:12,944 INFO L225 Difference]: With dead ends: 104 [2022-03-18 23:07:12,944 INFO L226 Difference]: Without dead ends: 85 [2022-03-18 23:07:12,944 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 48 GetRequests, 39 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=40, Invalid=70, Unknown=0, NotChecked=0, Total=110 [2022-03-18 23:07:12,944 INFO L912 BasicCegarLoop]: 61 mSDtfsCounter, 59 mSDsluCounter, 225 mSDsCounter, 0 mSdLazyCounter, 85 mSolverCounterSat, 11 mSolverCounterUnsat, 5 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 13.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 59 SdHoareTripleChecker+Valid, 286 SdHoareTripleChecker+Invalid, 101 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 85 IncrementalHoareTripleChecker+Invalid, 5 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 13.3s IncrementalHoareTripleChecker+Time [2022-03-18 23:07:12,945 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [59 Valid, 286 Invalid, 101 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 85 Invalid, 5 Unknown, 0 Unchecked, 13.3s Time] [2022-03-18 23:07:12,945 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 85 states. [2022-03-18 23:07:12,951 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 85 to 63. [2022-03-18 23:07:12,951 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 38 states have (on average 1.263157894736842) internal successors, (48), 40 states have internal predecessors, (48), 19 states have call successors, (19), 6 states have call predecessors, (19), 5 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-03-18 23:07:12,952 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 83 transitions. [2022-03-18 23:07:12,952 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 83 transitions. Word has length 23 [2022-03-18 23:07:12,952 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 23:07:12,952 INFO L478 AbstractCegarLoop]: Abstraction has 63 states and 83 transitions. [2022-03-18 23:07:12,952 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.625) internal successors, (29), 8 states have internal predecessors, (29), 4 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2022-03-18 23:07:12,952 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 83 transitions. [2022-03-18 23:07:12,953 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2022-03-18 23:07:12,953 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 23:07:12,953 INFO L500 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 23:07:12,978 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-03-18 23:07:13,169 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 23:07:13,169 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 23:07:13,169 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 23:07:13,170 INFO L85 PathProgramCache]: Analyzing trace with hash -1731080004, now seen corresponding path program 1 times [2022-03-18 23:07:13,170 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 23:07:13,170 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1672848531] [2022-03-18 23:07:13,170 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 23:07:13,170 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 23:07:13,179 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 23:07:13,179 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1670573823] [2022-03-18 23:07:13,179 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 23:07:13,179 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 23:07:13,179 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 23:07:13,183 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) [2022-03-18 23:07:13,186 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-03-18 23:07:13,212 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 23:07:13,212 INFO L263 TraceCheckSpWp]: Trace formula consists of 94 conjuncts, 9 conjunts are in the unsatisfiable core [2022-03-18 23:07:13,213 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 23:07:13,270 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-18 23:07:13,271 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 23:07:13,327 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-18 23:07:13,327 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 23:07:13,327 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1672848531] [2022-03-18 23:07:13,327 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 23:07:13,327 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1670573823] [2022-03-18 23:07:13,327 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1670573823] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-18 23:07:13,327 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-18 23:07:13,327 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2022-03-18 23:07:13,327 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [901465931] [2022-03-18 23:07:13,327 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-18 23:07:13,328 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-03-18 23:07:13,328 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 23:07:13,328 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-03-18 23:07:13,328 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=46, Unknown=0, NotChecked=0, Total=72 [2022-03-18 23:07:13,328 INFO L87 Difference]: Start difference. First operand 63 states and 83 transitions. Second operand has 9 states, 9 states have (on average 3.6666666666666665) internal successors, (33), 9 states have internal predecessors, (33), 4 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2022-03-18 23:07:18,130 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-03-18 23:07:20,204 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-03-18 23:07:22,183 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.13s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 23:07:23,538 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 23:07:23,538 INFO L93 Difference]: Finished difference Result 116 states and 158 transitions. [2022-03-18 23:07:23,538 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-03-18 23:07:23,538 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 3.6666666666666665) internal successors, (33), 9 states have internal predecessors, (33), 4 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) Word has length 24 [2022-03-18 23:07:23,539 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 23:07:23,539 INFO L225 Difference]: With dead ends: 116 [2022-03-18 23:07:23,539 INFO L226 Difference]: Without dead ends: 107 [2022-03-18 23:07:23,540 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 50 GetRequests, 39 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=46, Invalid=86, Unknown=0, NotChecked=0, Total=132 [2022-03-18 23:07:23,540 INFO L912 BasicCegarLoop]: 70 mSDtfsCounter, 103 mSDsluCounter, 157 mSDsCounter, 0 mSdLazyCounter, 91 mSolverCounterSat, 39 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 10.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 103 SdHoareTripleChecker+Valid, 227 SdHoareTripleChecker+Invalid, 132 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 39 IncrementalHoareTripleChecker+Valid, 91 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 10.2s IncrementalHoareTripleChecker+Time [2022-03-18 23:07:23,540 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [103 Valid, 227 Invalid, 132 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [39 Valid, 91 Invalid, 2 Unknown, 0 Unchecked, 10.2s Time] [2022-03-18 23:07:23,541 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 107 states. [2022-03-18 23:07:23,551 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 107 to 100. [2022-03-18 23:07:23,551 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 100 states, 55 states have (on average 1.309090909090909) internal successors, (72), 59 states have internal predecessors, (72), 37 states have call successors, (37), 8 states have call predecessors, (37), 7 states have return successors, (32), 32 states have call predecessors, (32), 32 states have call successors, (32) [2022-03-18 23:07:23,552 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 100 states to 100 states and 141 transitions. [2022-03-18 23:07:23,552 INFO L78 Accepts]: Start accepts. Automaton has 100 states and 141 transitions. Word has length 24 [2022-03-18 23:07:23,552 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 23:07:23,553 INFO L478 AbstractCegarLoop]: Abstraction has 100 states and 141 transitions. [2022-03-18 23:07:23,553 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 3.6666666666666665) internal successors, (33), 9 states have internal predecessors, (33), 4 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2022-03-18 23:07:23,553 INFO L276 IsEmpty]: Start isEmpty. Operand 100 states and 141 transitions. [2022-03-18 23:07:23,553 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2022-03-18 23:07:23,553 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 23:07:23,553 INFO L500 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 23:07:23,573 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-03-18 23:07:23,773 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 23:07:23,773 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 23:07:23,774 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 23:07:23,774 INFO L85 PathProgramCache]: Analyzing trace with hash -1729947946, now seen corresponding path program 1 times [2022-03-18 23:07:23,774 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 23:07:23,774 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [845296587] [2022-03-18 23:07:23,774 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 23:07:23,774 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 23:07:23,788 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 23:07:23,905 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-18 23:07:23,906 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 23:07:23,913 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-18 23:07:23,914 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 23:07:23,922 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-18 23:07:23,922 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 23:07:23,922 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [845296587] [2022-03-18 23:07:23,922 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [845296587] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-18 23:07:23,922 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1483423826] [2022-03-18 23:07:23,922 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 23:07:23,922 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 23:07:23,922 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 23:07:23,923 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) [2022-03-18 23:07:23,924 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-03-18 23:07:23,966 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 23:07:23,966 INFO L263 TraceCheckSpWp]: Trace formula consists of 94 conjuncts, 12 conjunts are in the unsatisfiable core [2022-03-18 23:07:23,967 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 23:07:24,108 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-18 23:07:24,108 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 23:07:24,245 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-18 23:07:24,245 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1483423826] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-18 23:07:24,245 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-18 23:07:24,245 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7, 7] total 15 [2022-03-18 23:07:24,245 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1328444103] [2022-03-18 23:07:24,246 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-03-18 23:07:24,246 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-03-18 23:07:24,246 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 23:07:24,246 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-03-18 23:07:24,246 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=44, Invalid=166, Unknown=0, NotChecked=0, Total=210 [2022-03-18 23:07:24,246 INFO L87 Difference]: Start difference. First operand 100 states and 141 transitions. Second operand has 15 states, 15 states have (on average 2.4) internal successors, (36), 12 states have internal predecessors, (36), 4 states have call successors, (7), 4 states have call predecessors, (7), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-18 23:07:28,099 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-03-18 23:07:33,034 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-03-18 23:07:37,643 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-03-18 23:07:39,653 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-03-18 23:07:41,874 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 23:07:41,874 INFO L93 Difference]: Finished difference Result 156 states and 225 transitions. [2022-03-18 23:07:41,874 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-03-18 23:07:41,874 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.4) internal successors, (36), 12 states have internal predecessors, (36), 4 states have call successors, (7), 4 states have call predecessors, (7), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 24 [2022-03-18 23:07:41,875 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 23:07:41,875 INFO L225 Difference]: With dead ends: 156 [2022-03-18 23:07:41,876 INFO L226 Difference]: Without dead ends: 141 [2022-03-18 23:07:41,876 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 43 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 75 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=95, Invalid=367, Unknown=0, NotChecked=0, Total=462 [2022-03-18 23:07:41,877 INFO L912 BasicCegarLoop]: 60 mSDtfsCounter, 63 mSDsluCounter, 216 mSDsCounter, 0 mSdLazyCounter, 422 mSolverCounterSat, 174 mSolverCounterUnsat, 4 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 17.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 72 SdHoareTripleChecker+Valid, 276 SdHoareTripleChecker+Invalid, 600 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 174 IncrementalHoareTripleChecker+Valid, 422 IncrementalHoareTripleChecker+Invalid, 4 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 17.5s IncrementalHoareTripleChecker+Time [2022-03-18 23:07:41,878 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [72 Valid, 276 Invalid, 600 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [174 Valid, 422 Invalid, 4 Unknown, 0 Unchecked, 17.5s Time] [2022-03-18 23:07:41,878 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 141 states. [2022-03-18 23:07:41,893 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 141 to 134. [2022-03-18 23:07:41,893 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 134 states, 74 states have (on average 1.2702702702702702) internal successors, (94), 80 states have internal predecessors, (94), 49 states have call successors, (49), 11 states have call predecessors, (49), 10 states have return successors, (43), 42 states have call predecessors, (43), 43 states have call successors, (43) [2022-03-18 23:07:41,894 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 134 states to 134 states and 186 transitions. [2022-03-18 23:07:41,894 INFO L78 Accepts]: Start accepts. Automaton has 134 states and 186 transitions. Word has length 24 [2022-03-18 23:07:41,894 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 23:07:41,894 INFO L478 AbstractCegarLoop]: Abstraction has 134 states and 186 transitions. [2022-03-18 23:07:41,895 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.4) internal successors, (36), 12 states have internal predecessors, (36), 4 states have call successors, (7), 4 states have call predecessors, (7), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-18 23:07:41,895 INFO L276 IsEmpty]: Start isEmpty. Operand 134 states and 186 transitions. [2022-03-18 23:07:41,895 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2022-03-18 23:07:41,895 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 23:07:41,895 INFO L500 BasicCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 23:07:41,916 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-03-18 23:07:42,113 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 23:07:42,113 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 23:07:42,113 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 23:07:42,113 INFO L85 PathProgramCache]: Analyzing trace with hash -2026335537, now seen corresponding path program 1 times [2022-03-18 23:07:42,113 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 23:07:42,113 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [413830521] [2022-03-18 23:07:42,114 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 23:07:42,114 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 23:07:42,119 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 23:07:42,120 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1228528938] [2022-03-18 23:07:42,120 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 23:07:42,120 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 23:07:42,120 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 23:07:42,123 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) [2022-03-18 23:07:42,141 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-03-18 23:07:42,226 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 23:07:42,227 INFO L263 TraceCheckSpWp]: Trace formula consists of 104 conjuncts, 9 conjunts are in the unsatisfiable core [2022-03-18 23:07:42,229 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 23:07:42,326 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-18 23:07:42,326 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-18 23:07:42,326 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 23:07:42,326 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [413830521] [2022-03-18 23:07:42,326 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 23:07:42,326 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1228528938] [2022-03-18 23:07:42,327 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1228528938] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-18 23:07:42,327 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-18 23:07:42,327 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-18 23:07:42,327 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1364106182] [2022-03-18 23:07:42,327 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-18 23:07:42,327 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-18 23:07:42,327 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 23:07:42,327 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-18 23:07:42,327 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-18 23:07:42,328 INFO L87 Difference]: Start difference. First operand 134 states and 186 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-18 23:07:43,111 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 23:07:43,112 INFO L93 Difference]: Finished difference Result 140 states and 190 transitions. [2022-03-18 23:07:43,112 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-18 23:07:43,112 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 31 [2022-03-18 23:07:43,112 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 23:07:43,114 INFO L225 Difference]: With dead ends: 140 [2022-03-18 23:07:43,114 INFO L226 Difference]: Without dead ends: 116 [2022-03-18 23:07:43,114 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 31 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-03-18 23:07:43,115 INFO L912 BasicCegarLoop]: 49 mSDtfsCounter, 6 mSDsluCounter, 122 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 171 SdHoareTripleChecker+Invalid, 41 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2022-03-18 23:07:43,115 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 171 Invalid, 41 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2022-03-18 23:07:43,115 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 116 states. [2022-03-18 23:07:43,124 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 116 to 116. [2022-03-18 23:07:43,124 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 116 states, 65 states have (on average 1.2769230769230768) internal successors, (83), 70 states have internal predecessors, (83), 42 states have call successors, (42), 9 states have call predecessors, (42), 8 states have return successors, (37), 36 states have call predecessors, (37), 37 states have call successors, (37) [2022-03-18 23:07:43,125 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 116 states to 116 states and 162 transitions. [2022-03-18 23:07:43,125 INFO L78 Accepts]: Start accepts. Automaton has 116 states and 162 transitions. Word has length 31 [2022-03-18 23:07:43,125 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 23:07:43,125 INFO L478 AbstractCegarLoop]: Abstraction has 116 states and 162 transitions. [2022-03-18 23:07:43,125 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-18 23:07:43,125 INFO L276 IsEmpty]: Start isEmpty. Operand 116 states and 162 transitions. [2022-03-18 23:07:43,126 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2022-03-18 23:07:43,126 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 23:07:43,126 INFO L500 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 23:07:43,131 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-03-18 23:07:43,330 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 23:07:43,330 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 23:07:43,330 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 23:07:43,330 INFO L85 PathProgramCache]: Analyzing trace with hash -266035918, now seen corresponding path program 1 times [2022-03-18 23:07:43,331 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 23:07:43,331 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1135331771] [2022-03-18 23:07:43,331 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 23:07:43,331 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 23:07:43,337 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 23:07:43,337 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1864189866] [2022-03-18 23:07:43,337 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 23:07:43,337 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 23:07:43,337 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 23:07:43,349 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 23:07:43,350 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-03-18 23:07:43,415 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 23:07:43,416 INFO L263 TraceCheckSpWp]: Trace formula consists of 112 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-18 23:07:43,417 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 23:07:43,506 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2022-03-18 23:07:43,506 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-18 23:07:43,506 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 23:07:43,506 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1135331771] [2022-03-18 23:07:43,506 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 23:07:43,506 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1864189866] [2022-03-18 23:07:43,506 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1864189866] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-18 23:07:43,506 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-18 23:07:43,507 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-18 23:07:43,507 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [13334969] [2022-03-18 23:07:43,507 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-18 23:07:43,507 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-18 23:07:43,507 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 23:07:43,507 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-18 23:07:43,507 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-18 23:07:43,507 INFO L87 Difference]: Start difference. First operand 116 states and 162 transitions. Second operand has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-18 23:07:43,904 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 23:07:43,904 INFO L93 Difference]: Finished difference Result 138 states and 180 transitions. [2022-03-18 23:07:43,905 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-18 23:07:43,905 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 34 [2022-03-18 23:07:43,905 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 23:07:43,906 INFO L225 Difference]: With dead ends: 138 [2022-03-18 23:07:43,906 INFO L226 Difference]: Without dead ends: 134 [2022-03-18 23:07:43,906 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-03-18 23:07:43,906 INFO L912 BasicCegarLoop]: 50 mSDtfsCounter, 8 mSDsluCounter, 122 mSDsCounter, 0 mSdLazyCounter, 30 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 172 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 30 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-03-18 23:07:43,906 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 172 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 30 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2022-03-18 23:07:43,907 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 134 states. [2022-03-18 23:07:43,915 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 134 to 131. [2022-03-18 23:07:43,915 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 131 states, 77 states have (on average 1.155844155844156) internal successors, (89), 80 states have internal predecessors, (89), 40 states have call successors, (40), 14 states have call predecessors, (40), 13 states have return successors, (37), 36 states have call predecessors, (37), 37 states have call successors, (37) [2022-03-18 23:07:43,916 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 131 states to 131 states and 166 transitions. [2022-03-18 23:07:43,916 INFO L78 Accepts]: Start accepts. Automaton has 131 states and 166 transitions. Word has length 34 [2022-03-18 23:07:43,916 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 23:07:43,916 INFO L478 AbstractCegarLoop]: Abstraction has 131 states and 166 transitions. [2022-03-18 23:07:43,916 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-18 23:07:43,916 INFO L276 IsEmpty]: Start isEmpty. Operand 131 states and 166 transitions. [2022-03-18 23:07:43,917 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2022-03-18 23:07:43,917 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 23:07:43,917 INFO L500 BasicCegarLoop]: trace histogram [5, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 23:07:43,925 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2022-03-18 23:07:44,123 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 23:07:44,125 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 23:07:44,126 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 23:07:44,126 INFO L85 PathProgramCache]: Analyzing trace with hash 1209382940, now seen corresponding path program 1 times [2022-03-18 23:07:44,126 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 23:07:44,126 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [833611047] [2022-03-18 23:07:44,126 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 23:07:44,126 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 23:07:44,134 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 23:07:44,187 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-18 23:07:44,188 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 23:07:44,192 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-18 23:07:44,194 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 23:07:44,196 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-18 23:07:44,196 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 23:07:44,196 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [833611047] [2022-03-18 23:07:44,196 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [833611047] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-18 23:07:44,196 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [338732960] [2022-03-18 23:07:44,196 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 23:07:44,196 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 23:07:44,196 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 23:07:44,197 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 23:07:44,199 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-03-18 23:07:44,225 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 23:07:44,226 INFO L263 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 13 conjunts are in the unsatisfiable core [2022-03-18 23:07:44,227 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 23:07:44,303 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-18 23:07:44,303 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 23:07:44,371 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-18 23:07:44,372 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [338732960] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-18 23:07:44,372 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-18 23:07:44,372 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8, 8] total 9 [2022-03-18 23:07:44,372 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [843377772] [2022-03-18 23:07:44,372 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-03-18 23:07:44,372 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-03-18 23:07:44,372 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 23:07:44,372 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-03-18 23:07:44,373 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=25, Invalid=47, Unknown=0, NotChecked=0, Total=72 [2022-03-18 23:07:44,373 INFO L87 Difference]: Start difference. First operand 131 states and 166 transitions. Second operand has 9 states, 9 states have (on average 3.3333333333333335) internal successors, (30), 8 states have internal predecessors, (30), 3 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2022-03-18 23:07:46,665 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 23:07:50,648 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-03-18 23:07:51,447 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 23:07:51,448 INFO L93 Difference]: Finished difference Result 185 states and 233 transitions. [2022-03-18 23:07:51,448 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2022-03-18 23:07:51,448 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 3.3333333333333335) internal successors, (30), 8 states have internal predecessors, (30), 3 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) Word has length 32 [2022-03-18 23:07:51,448 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 23:07:51,449 INFO L225 Difference]: With dead ends: 185 [2022-03-18 23:07:51,449 INFO L226 Difference]: Without dead ends: 145 [2022-03-18 23:07:51,449 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 83 GetRequests, 68 SyntacticMatches, 1 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 33 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=73, Invalid=167, Unknown=0, NotChecked=0, Total=240 [2022-03-18 23:07:51,450 INFO L912 BasicCegarLoop]: 47 mSDtfsCounter, 55 mSDsluCounter, 85 mSDsCounter, 0 mSdLazyCounter, 202 mSolverCounterSat, 41 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 7.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 64 SdHoareTripleChecker+Valid, 132 SdHoareTripleChecker+Invalid, 245 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 41 IncrementalHoareTripleChecker+Valid, 202 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 7.0s IncrementalHoareTripleChecker+Time [2022-03-18 23:07:51,450 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [64 Valid, 132 Invalid, 245 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [41 Valid, 202 Invalid, 2 Unknown, 0 Unchecked, 7.0s Time] [2022-03-18 23:07:51,450 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 145 states. [2022-03-18 23:07:51,458 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 145 to 142. [2022-03-18 23:07:51,459 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 142 states, 86 states have (on average 1.1627906976744187) internal successors, (100), 89 states have internal predecessors, (100), 40 states have call successors, (40), 16 states have call predecessors, (40), 15 states have return successors, (37), 36 states have call predecessors, (37), 37 states have call successors, (37) [2022-03-18 23:07:51,459 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 142 states to 142 states and 177 transitions. [2022-03-18 23:07:51,460 INFO L78 Accepts]: Start accepts. Automaton has 142 states and 177 transitions. Word has length 32 [2022-03-18 23:07:51,460 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 23:07:51,460 INFO L478 AbstractCegarLoop]: Abstraction has 142 states and 177 transitions. [2022-03-18 23:07:51,460 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 3.3333333333333335) internal successors, (30), 8 states have internal predecessors, (30), 3 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2022-03-18 23:07:51,460 INFO L276 IsEmpty]: Start isEmpty. Operand 142 states and 177 transitions. [2022-03-18 23:07:51,461 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2022-03-18 23:07:51,461 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 23:07:51,461 INFO L500 BasicCegarLoop]: trace histogram [6, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 23:07:51,479 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2022-03-18 23:07:51,675 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2022-03-18 23:07:51,675 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 23:07:51,676 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 23:07:51,676 INFO L85 PathProgramCache]: Analyzing trace with hash -55903719, now seen corresponding path program 2 times [2022-03-18 23:07:51,676 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 23:07:51,676 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [16471474] [2022-03-18 23:07:51,676 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 23:07:51,676 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 23:07:51,697 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 23:07:51,731 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-18 23:07:51,732 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 23:07:51,735 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-18 23:07:51,736 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 23:07:51,738 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2022-03-18 23:07:51,738 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 23:07:51,738 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [16471474] [2022-03-18 23:07:51,738 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [16471474] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-18 23:07:51,738 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-18 23:07:51,739 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-18 23:07:51,739 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2128107820] [2022-03-18 23:07:51,739 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-18 23:07:51,739 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-18 23:07:51,739 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 23:07:51,740 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-18 23:07:51,740 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-03-18 23:07:51,740 INFO L87 Difference]: Start difference. First operand 142 states and 177 transitions. Second operand has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-18 23:07:53,379 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 23:07:53,380 INFO L93 Difference]: Finished difference Result 179 states and 226 transitions. [2022-03-18 23:07:53,380 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-03-18 23:07:53,380 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 35 [2022-03-18 23:07:53,381 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 23:07:53,381 INFO L225 Difference]: With dead ends: 179 [2022-03-18 23:07:53,381 INFO L226 Difference]: Without dead ends: 139 [2022-03-18 23:07:53,382 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-03-18 23:07:53,382 INFO L912 BasicCegarLoop]: 42 mSDtfsCounter, 10 mSDsluCounter, 64 mSDsCounter, 0 mSdLazyCounter, 102 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 106 SdHoareTripleChecker+Invalid, 114 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 102 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.6s IncrementalHoareTripleChecker+Time [2022-03-18 23:07:53,382 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 106 Invalid, 114 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 102 Invalid, 0 Unknown, 0 Unchecked, 1.6s Time] [2022-03-18 23:07:53,383 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 139 states. [2022-03-18 23:07:53,391 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 139 to 134. [2022-03-18 23:07:53,391 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 134 states, 79 states have (on average 1.1518987341772151) internal successors, (91), 81 states have internal predecessors, (91), 39 states have call successors, (39), 16 states have call predecessors, (39), 15 states have return successors, (36), 36 states have call predecessors, (36), 36 states have call successors, (36) [2022-03-18 23:07:53,392 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 134 states to 134 states and 166 transitions. [2022-03-18 23:07:53,392 INFO L78 Accepts]: Start accepts. Automaton has 134 states and 166 transitions. Word has length 35 [2022-03-18 23:07:53,392 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 23:07:53,392 INFO L478 AbstractCegarLoop]: Abstraction has 134 states and 166 transitions. [2022-03-18 23:07:53,392 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-18 23:07:53,392 INFO L276 IsEmpty]: Start isEmpty. Operand 134 states and 166 transitions. [2022-03-18 23:07:53,394 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2022-03-18 23:07:53,394 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 23:07:53,394 INFO L500 BasicCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 23:07:53,394 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10 [2022-03-18 23:07:53,394 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 23:07:53,394 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 23:07:53,394 INFO L85 PathProgramCache]: Analyzing trace with hash -926681017, now seen corresponding path program 1 times [2022-03-18 23:07:53,394 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 23:07:53,394 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [624898796] [2022-03-18 23:07:53,394 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 23:07:53,394 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 23:07:53,406 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 23:07:53,406 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1026091577] [2022-03-18 23:07:53,406 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 23:07:53,407 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 23:07:53,407 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 23:07:53,412 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 23:07:53,413 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process