/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/hard2_unwindbound50.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-7390193 [2022-04-05 08:25:03,589 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-05 08:25:03,617 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-05 08:25:03,661 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-05 08:25:03,662 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-05 08:25:03,663 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-05 08:25:03,666 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-05 08:25:03,668 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-05 08:25:03,670 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-05 08:25:03,674 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-05 08:25:03,675 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-05 08:25:03,676 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-05 08:25:03,677 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-05 08:25:03,679 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-05 08:25:03,679 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-05 08:25:03,682 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-05 08:25:03,683 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-05 08:25:03,683 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-05 08:25:03,685 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-05 08:25:03,690 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-05 08:25:03,692 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-05 08:25:03,693 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-05 08:25:03,693 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-05 08:25:03,694 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-05 08:25:03,695 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-05 08:25:03,701 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-05 08:25:03,701 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-05 08:25:03,701 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-05 08:25:03,702 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-05 08:25:03,703 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-05 08:25:03,704 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-05 08:25:03,704 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-05 08:25:03,706 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-05 08:25:03,706 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-05 08:25:03,707 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-05 08:25:03,707 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-05 08:25:03,708 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-05 08:25:03,708 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-05 08:25:03,708 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-05 08:25:03,708 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-05 08:25:03,709 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-05 08:25:03,710 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-05 08:25:03,711 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/loopacceleration/qvasr/qvasr_64.epf [2022-04-05 08:25:03,735 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-05 08:25:03,735 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-05 08:25:03,736 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-04-05 08:25:03,736 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-04-05 08:25:03,737 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-04-05 08:25:03,738 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-04-05 08:25:03,738 INFO L138 SettingsManager]: * Use SBE=true [2022-04-05 08:25:03,738 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-05 08:25:03,738 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-05 08:25:03,739 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-05 08:25:03,739 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-05 08:25:03,739 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-05 08:25:03,739 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-05 08:25:03,739 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-05 08:25:03,739 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-05 08:25:03,739 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-05 08:25:03,740 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-05 08:25:03,740 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-05 08:25:03,740 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-05 08:25:03,740 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-05 08:25:03,740 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-05 08:25:03,740 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-04-05 08:25:03,741 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-04-05 08:25:03,741 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-04-05 08:25:03,741 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-04-05 08:25:03,741 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-05 08:25:03,741 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2022-04-05 08:25:03,741 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2022-04-05 08:25:03,742 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-04-05 08:25:03,742 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-04-05 08:25:03,950 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-05 08:25:03,979 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-05 08:25:03,980 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-05 08:25:03,981 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-05 08:25:03,982 INFO L275 PluginConnector]: CDTParser initialized [2022-04-05 08:25:03,982 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound50.c [2022-04-05 08:25:04,049 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/1eb90539b/433b86754e504d0094b267229c7e3ab7/FLAGf13755215 [2022-04-05 08:25:04,437 INFO L306 CDTParser]: Found 1 translation units. [2022-04-05 08:25:04,438 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound50.c [2022-04-05 08:25:04,444 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/1eb90539b/433b86754e504d0094b267229c7e3ab7/FLAGf13755215 [2022-04-05 08:25:04,852 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/1eb90539b/433b86754e504d0094b267229c7e3ab7 [2022-04-05 08:25:04,854 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-05 08:25:04,856 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-04-05 08:25:04,858 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-05 08:25:04,858 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-05 08:25:04,861 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-05 08:25:04,862 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 05.04 08:25:04" (1/1) ... [2022-04-05 08:25:04,863 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@ed06528 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 08:25:04, skipping insertion in model container [2022-04-05 08:25:04,863 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 05.04 08:25:04" (1/1) ... [2022-04-05 08:25:04,869 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-05 08:25:04,883 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-05 08:25:05,010 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/hard2_unwindbound50.c[526,539] [2022-04-05 08:25:05,025 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-05 08:25:05,034 INFO L203 MainTranslator]: Completed pre-run [2022-04-05 08:25:05,043 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/hard2_unwindbound50.c[526,539] [2022-04-05 08:25:05,048 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-05 08:25:05,058 INFO L208 MainTranslator]: Completed translation [2022-04-05 08:25:05,058 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 08:25:05 WrapperNode [2022-04-05 08:25:05,059 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-05 08:25:05,060 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-05 08:25:05,060 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-05 08:25:05,060 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-05 08:25:05,069 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 08:25:05" (1/1) ... [2022-04-05 08:25:05,069 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 08:25:05" (1/1) ... [2022-04-05 08:25:05,075 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 08:25:05" (1/1) ... [2022-04-05 08:25:05,075 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 08:25:05" (1/1) ... [2022-04-05 08:25:05,088 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 08:25:05" (1/1) ... [2022-04-05 08:25:05,094 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 08:25:05" (1/1) ... [2022-04-05 08:25:05,099 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 08:25:05" (1/1) ... [2022-04-05 08:25:05,100 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-05 08:25:05,101 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-05 08:25:05,101 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-05 08:25:05,101 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-05 08:25:05,104 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 08:25:05" (1/1) ... [2022-04-05 08:25:05,109 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-05 08:25:05,117 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 08:25:05,133 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-04-05 08:25:05,146 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-04-05 08:25:05,168 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-05 08:25:05,169 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-05 08:25:05,169 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-05 08:25:05,169 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-05 08:25:05,170 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-05 08:25:05,170 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-05 08:25:05,170 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-05 08:25:05,170 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-05 08:25:05,170 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-05 08:25:05,171 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-05 08:25:05,171 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-04-05 08:25:05,171 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-05 08:25:05,171 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-05 08:25:05,171 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-05 08:25:05,171 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-05 08:25:05,171 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-05 08:25:05,171 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-05 08:25:05,172 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-05 08:25:05,172 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-05 08:25:05,172 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-05 08:25:05,221 INFO L234 CfgBuilder]: Building ICFG [2022-04-05 08:25:05,223 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-05 08:25:05,386 INFO L275 CfgBuilder]: Performing block encoding [2022-04-05 08:25:05,391 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-05 08:25:05,391 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-04-05 08:25:05,393 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 05.04 08:25:05 BoogieIcfgContainer [2022-04-05 08:25:05,393 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-05 08:25:05,393 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-04-05 08:25:05,393 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-04-05 08:25:05,394 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-04-05 08:25:05,397 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 05.04 08:25:05" (1/1) ... [2022-04-05 08:25:05,398 INFO L168 ansformationObserver]: Applying ICFG transformation LOOP_ACCELERATION_QVASR [2022-04-05 08:25:05,410 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 05.04 08:25:05 BasicIcfg [2022-04-05 08:25:05,410 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-04-05 08:25:05,411 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-05 08:25:05,411 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-05 08:25:05,414 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-05 08:25:05,414 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 05.04 08:25:04" (1/4) ... [2022-04-05 08:25:05,414 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@35450416 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 05.04 08:25:05, skipping insertion in model container [2022-04-05 08:25:05,415 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 08:25:05" (2/4) ... [2022-04-05 08:25:05,415 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@35450416 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 05.04 08:25:05, skipping insertion in model container [2022-04-05 08:25:05,415 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 05.04 08:25:05" (3/4) ... [2022-04-05 08:25:05,415 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@35450416 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 05.04 08:25:05, skipping insertion in model container [2022-04-05 08:25:05,415 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 05.04 08:25:05" (4/4) ... [2022-04-05 08:25:05,416 INFO L111 eAbstractionObserver]: Analyzing ICFG hard2_unwindbound50.cqvasr [2022-04-05 08:25:05,420 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-04-05 08:25:05,420 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-05 08:25:05,452 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-05 08:25:05,457 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-04-05 08:25:05,457 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-05 08:25:05,470 INFO L276 IsEmpty]: Start isEmpty. Operand has 31 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 18 states have internal predecessors, (26), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-05 08:25:05,478 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-04-05 08:25:05,478 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:25:05,478 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:25:05,479 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:25:05,482 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:25:05,483 INFO L85 PathProgramCache]: Analyzing trace with hash 121155216, now seen corresponding path program 1 times [2022-04-05 08:25:05,489 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:25:05,490 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [318289040] [2022-04-05 08:25:05,490 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:25:05,490 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:25:05,578 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:25:05,653 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-05 08:25:05,656 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:25:05,662 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 08:25:05,663 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:25:05,664 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [318289040] [2022-04-05 08:25:05,665 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [318289040] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 08:25:05,665 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 08:25:05,665 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-05 08:25:05,666 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [93549847] [2022-04-05 08:25:05,667 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 08:25:05,671 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-05 08:25:05,671 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:25:05,705 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-05 08:25:05,706 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-05 08:25:05,707 INFO L87 Difference]: Start difference. First operand has 31 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 18 states have internal predecessors, (26), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-05 08:25:05,804 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:25:05,805 INFO L93 Difference]: Finished difference Result 57 states and 91 transitions. [2022-04-05 08:25:05,806 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-05 08:25:05,807 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2022-04-05 08:25:05,807 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:25:05,813 INFO L225 Difference]: With dead ends: 57 [2022-04-05 08:25:05,813 INFO L226 Difference]: Without dead ends: 27 [2022-04-05 08:25:05,816 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 3 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-04-05 08:25:05,823 INFO L913 BasicCegarLoop]: 40 mSDtfsCounter, 6 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 23 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 44 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 23 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 08:25:05,824 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 44 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 23 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 08:25:05,836 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2022-04-05 08:25:05,849 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 26. [2022-04-05 08:25:05,850 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 15 states have internal predecessors, (20), 9 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-05 08:25:05,851 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 36 transitions. [2022-04-05 08:25:05,852 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 36 transitions. Word has length 12 [2022-04-05 08:25:05,853 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:25:05,853 INFO L478 AbstractCegarLoop]: Abstraction has 26 states and 36 transitions. [2022-04-05 08:25:05,853 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-05 08:25:05,853 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 36 transitions. [2022-04-05 08:25:05,854 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-04-05 08:25:05,854 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:25:05,854 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:25:05,854 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-05 08:25:05,855 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:25:05,855 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:25:05,855 INFO L85 PathProgramCache]: Analyzing trace with hash 152644303, now seen corresponding path program 1 times [2022-04-05 08:25:05,856 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:25:05,856 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [265555567] [2022-04-05 08:25:05,856 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:25:05,856 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:25:05,874 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:25:05,923 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-05 08:25:05,926 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:25:05,932 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 08:25:05,932 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:25:05,932 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [265555567] [2022-04-05 08:25:05,932 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [265555567] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 08:25:05,932 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 08:25:05,933 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-05 08:25:05,933 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2012709915] [2022-04-05 08:25:05,933 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 08:25:05,934 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-05 08:25:05,934 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:25:05,935 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-05 08:25:05,935 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-04-05 08:25:05,935 INFO L87 Difference]: Start difference. First operand 26 states and 36 transitions. Second operand has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-05 08:25:06,104 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:25:06,104 INFO L93 Difference]: Finished difference Result 41 states and 56 transitions. [2022-04-05 08:25:06,105 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-05 08:25:06,105 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2022-04-05 08:25:06,105 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:25:06,107 INFO L225 Difference]: With dead ends: 41 [2022-04-05 08:25:06,108 INFO L226 Difference]: Without dead ends: 39 [2022-04-05 08:25:06,112 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-04-05 08:25:06,114 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 24 mSDsluCounter, 51 mSDsCounter, 0 mSdLazyCounter, 80 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 85 SdHoareTripleChecker+Invalid, 93 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 80 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 08:25:06,115 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [30 Valid, 85 Invalid, 93 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 80 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 08:25:06,118 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2022-04-05 08:25:06,133 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 30. [2022-04-05 08:25:06,133 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-05 08:25:06,134 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 39 transitions. [2022-04-05 08:25:06,134 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 39 transitions. Word has length 12 [2022-04-05 08:25:06,135 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:25:06,135 INFO L478 AbstractCegarLoop]: Abstraction has 30 states and 39 transitions. [2022-04-05 08:25:06,135 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-05 08:25:06,135 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 39 transitions. [2022-04-05 08:25:06,136 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2022-04-05 08:25:06,136 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:25:06,136 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:25:06,137 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-04-05 08:25:06,137 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:25:06,138 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:25:06,138 INFO L85 PathProgramCache]: Analyzing trace with hash -400958603, now seen corresponding path program 1 times [2022-04-05 08:25:06,138 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:25:06,138 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1370342309] [2022-04-05 08:25:06,139 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:25:06,139 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:25:06,149 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:25:06,209 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-05 08:25:06,213 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:25:06,224 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 08:25:06,224 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:25:06,224 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1370342309] [2022-04-05 08:25:06,224 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1370342309] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 08:25:06,225 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 08:25:06,225 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-05 08:25:06,225 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1228608241] [2022-04-05 08:25:06,225 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 08:25:06,225 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-05 08:25:06,226 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:25:06,226 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-05 08:25:06,226 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-05 08:25:06,226 INFO L87 Difference]: Start difference. First operand 30 states and 39 transitions. Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-05 08:25:06,303 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:25:06,303 INFO L93 Difference]: Finished difference Result 46 states and 61 transitions. [2022-04-05 08:25:06,304 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-05 08:25:06,304 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 14 [2022-04-05 08:25:06,304 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:25:06,305 INFO L225 Difference]: With dead ends: 46 [2022-04-05 08:25:06,306 INFO L226 Difference]: Without dead ends: 32 [2022-04-05 08:25:06,308 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 3 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-04-05 08:25:06,312 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 6 mSDsluCounter, 39 mSDsCounter, 0 mSdLazyCounter, 51 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 73 SdHoareTripleChecker+Invalid, 59 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 51 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 08:25:06,314 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 73 Invalid, 59 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 51 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 08:25:06,315 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2022-04-05 08:25:06,322 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2022-04-05 08:25:06,323 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-05 08:25:06,325 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 41 transitions. [2022-04-05 08:25:06,326 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 41 transitions. Word has length 14 [2022-04-05 08:25:06,326 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:25:06,326 INFO L478 AbstractCegarLoop]: Abstraction has 32 states and 41 transitions. [2022-04-05 08:25:06,326 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-05 08:25:06,327 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 41 transitions. [2022-04-05 08:25:06,327 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-04-05 08:25:06,327 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:25:06,327 INFO L499 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:25:06,328 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-04-05 08:25:06,328 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:25:06,329 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:25:06,329 INFO L85 PathProgramCache]: Analyzing trace with hash 185978583, now seen corresponding path program 1 times [2022-04-05 08:25:06,329 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:25:06,329 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [774398405] [2022-04-05 08:25:06,329 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:25:06,329 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:25:06,343 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:25:06,395 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-05 08:25:06,398 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:25:06,417 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2022-04-05 08:25:06,419 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:25:06,425 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 08:25:06,425 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:25:06,425 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [774398405] [2022-04-05 08:25:06,425 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [774398405] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 08:25:06,425 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 08:25:06,426 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-05 08:25:06,426 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [278289941] [2022-04-05 08:25:06,426 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 08:25:06,426 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-05 08:25:06,426 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:25:06,427 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-05 08:25:06,427 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-04-05 08:25:06,427 INFO L87 Difference]: Start difference. First operand 32 states and 41 transitions. Second operand has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-05 08:25:06,568 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:25:06,569 INFO L93 Difference]: Finished difference Result 46 states and 60 transitions. [2022-04-05 08:25:06,569 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-05 08:25:06,570 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 17 [2022-04-05 08:25:06,570 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:25:06,571 INFO L225 Difference]: With dead ends: 46 [2022-04-05 08:25:06,571 INFO L226 Difference]: Without dead ends: 44 [2022-04-05 08:25:06,572 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-04-05 08:25:06,579 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 19 mSDsluCounter, 44 mSDsCounter, 0 mSdLazyCounter, 93 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 78 SdHoareTripleChecker+Invalid, 106 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 93 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 08:25:06,580 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 78 Invalid, 106 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 93 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 08:25:06,582 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2022-04-05 08:25:06,593 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 36. [2022-04-05 08:25:06,594 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 23 states have internal predecessors, (28), 9 states have call successors, (9), 5 states have call predecessors, (9), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-05 08:25:06,594 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 44 transitions. [2022-04-05 08:25:06,595 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 44 transitions. Word has length 17 [2022-04-05 08:25:06,595 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:25:06,595 INFO L478 AbstractCegarLoop]: Abstraction has 36 states and 44 transitions. [2022-04-05 08:25:06,595 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-05 08:25:06,595 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 44 transitions. [2022-04-05 08:25:06,596 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2022-04-05 08:25:06,596 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:25:06,596 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:25:06,596 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2022-04-05 08:25:06,596 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:25:06,597 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:25:06,597 INFO L85 PathProgramCache]: Analyzing trace with hash -820589269, now seen corresponding path program 1 times [2022-04-05 08:25:06,597 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:25:06,597 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1366795691] [2022-04-05 08:25:06,597 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:25:06,597 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:25:06,620 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 08:25:06,620 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1324536728] [2022-04-05 08:25:06,620 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:25:06,626 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:25:06,626 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 08:25:06,631 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-04-05 08:25:06,665 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-04-05 08:25:06,685 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:25:06,687 INFO L263 TraceCheckSpWp]: Trace formula consists of 93 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-05 08:25:06,698 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 08:25:06,901 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-05 08:25:06,902 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-05 08:25:06,902 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:25:06,902 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1366795691] [2022-04-05 08:25:06,902 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 08:25:06,902 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1324536728] [2022-04-05 08:25:06,902 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1324536728] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 08:25:06,903 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 08:25:06,903 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-05 08:25:06,903 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1313257882] [2022-04-05 08:25:06,903 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 08:25:06,903 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-05 08:25:06,904 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:25:06,904 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-05 08:25:06,904 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-05 08:25:06,904 INFO L87 Difference]: Start difference. First operand 36 states and 44 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-05 08:25:06,961 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:25:06,961 INFO L93 Difference]: Finished difference Result 65 states and 87 transitions. [2022-04-05 08:25:06,963 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-05 08:25:06,963 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 22 [2022-04-05 08:25:06,963 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:25:06,964 INFO L225 Difference]: With dead ends: 65 [2022-04-05 08:25:06,964 INFO L226 Difference]: Without dead ends: 50 [2022-04-05 08:25:06,964 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 18 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-04-05 08:25:06,965 INFO L913 BasicCegarLoop]: 38 mSDtfsCounter, 10 mSDsluCounter, 83 mSDsCounter, 0 mSdLazyCounter, 46 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 121 SdHoareTripleChecker+Invalid, 49 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 46 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-05 08:25:06,965 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 121 Invalid, 49 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 46 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-05 08:25:06,965 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2022-04-05 08:25:06,972 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 50. [2022-04-05 08:25:06,973 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 29 states have (on average 1.2758620689655173) internal successors, (37), 31 states have internal predecessors, (37), 15 states have call successors, (15), 6 states have call predecessors, (15), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-05 08:25:06,973 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 64 transitions. [2022-04-05 08:25:06,973 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 64 transitions. Word has length 22 [2022-04-05 08:25:06,974 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:25:06,974 INFO L478 AbstractCegarLoop]: Abstraction has 50 states and 64 transitions. [2022-04-05 08:25:06,974 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-05 08:25:06,974 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 64 transitions. [2022-04-05 08:25:06,975 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2022-04-05 08:25:06,975 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:25:06,975 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:25:07,001 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-04-05 08:25:07,175 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:25:07,176 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:25:07,176 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:25:07,176 INFO L85 PathProgramCache]: Analyzing trace with hash 1259710898, now seen corresponding path program 1 times [2022-04-05 08:25:07,176 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:25:07,176 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [962247670] [2022-04-05 08:25:07,177 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:25:07,177 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:25:07,185 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 08:25:07,185 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [684942680] [2022-04-05 08:25:07,185 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:25:07,185 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:25:07,185 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 08:25:07,187 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-04-05 08:25:07,192 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-04-05 08:25:07,238 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:25:07,239 INFO L263 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-05 08:25:07,241 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 08:25:07,339 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-05 08:25:07,339 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-05 08:25:07,340 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:25:07,340 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [962247670] [2022-04-05 08:25:07,340 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 08:25:07,340 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [684942680] [2022-04-05 08:25:07,340 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [684942680] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 08:25:07,340 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 08:25:07,340 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-05 08:25:07,340 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1124418986] [2022-04-05 08:25:07,341 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 08:25:07,341 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-05 08:25:07,341 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:25:07,342 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-05 08:25:07,342 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-04-05 08:25:07,342 INFO L87 Difference]: Start difference. First operand 50 states and 64 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-05 08:25:07,375 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:25:07,375 INFO L93 Difference]: Finished difference Result 70 states and 80 transitions. [2022-04-05 08:25:07,376 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-05 08:25:07,376 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 30 [2022-04-05 08:25:07,376 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:25:07,377 INFO L225 Difference]: With dead ends: 70 [2022-04-05 08:25:07,377 INFO L226 Difference]: Without dead ends: 63 [2022-04-05 08:25:07,378 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 26 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-04-05 08:25:07,379 INFO L913 BasicCegarLoop]: 36 mSDtfsCounter, 3 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 19 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 19 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-05 08:25:07,379 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [3 Valid, 124 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 19 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-05 08:25:07,380 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2022-04-05 08:25:07,388 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 62. [2022-04-05 08:25:07,389 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 38 states have (on average 1.1842105263157894) internal successors, (45), 40 states have internal predecessors, (45), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-05 08:25:07,389 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 72 transitions. [2022-04-05 08:25:07,390 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 72 transitions. Word has length 30 [2022-04-05 08:25:07,390 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:25:07,390 INFO L478 AbstractCegarLoop]: Abstraction has 62 states and 72 transitions. [2022-04-05 08:25:07,390 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-05 08:25:07,390 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 72 transitions. [2022-04-05 08:25:07,391 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2022-04-05 08:25:07,391 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:25:07,391 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:25:07,420 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-04-05 08:25:07,616 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,SelfDestructingSolverStorable5 [2022-04-05 08:25:07,616 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:25:07,617 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:25:07,617 INFO L85 PathProgramCache]: Analyzing trace with hash 1260813165, now seen corresponding path program 1 times [2022-04-05 08:25:07,617 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:25:07,617 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2047467592] [2022-04-05 08:25:07,617 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:25:07,617 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:25:07,625 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 08:25:07,625 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1097751707] [2022-04-05 08:25:07,626 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:25:07,626 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:25:07,626 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 08:25:07,630 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-04-05 08:25:07,660 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-04-05 08:25:07,684 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:25:07,685 INFO L263 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-05 08:25:07,686 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 08:25:07,806 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-05 08:25:07,806 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-05 08:25:07,806 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:25:07,806 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2047467592] [2022-04-05 08:25:07,807 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 08:25:07,807 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1097751707] [2022-04-05 08:25:07,807 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1097751707] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 08:25:07,807 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 08:25:07,807 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-05 08:25:07,807 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1295483474] [2022-04-05 08:25:07,807 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 08:25:07,808 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-05 08:25:07,808 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:25:07,808 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-05 08:25:07,808 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-05 08:25:07,809 INFO L87 Difference]: Start difference. First operand 62 states and 72 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 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-04-05 08:25:07,858 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:25:07,858 INFO L93 Difference]: Finished difference Result 76 states and 91 transitions. [2022-04-05 08:25:07,861 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-05 08:25:07,862 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 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 30 [2022-04-05 08:25:07,863 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:25:07,868 INFO L225 Difference]: With dead ends: 76 [2022-04-05 08:25:07,869 INFO L226 Difference]: Without dead ends: 64 [2022-04-05 08:25:07,869 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 30 GetRequests, 26 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-04-05 08:25:07,870 INFO L913 BasicCegarLoop]: 29 mSDtfsCounter, 11 mSDsluCounter, 66 mSDsCounter, 0 mSdLazyCounter, 47 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 95 SdHoareTripleChecker+Invalid, 50 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 47 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-05 08:25:07,870 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 95 Invalid, 50 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 47 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-05 08:25:07,870 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2022-04-05 08:25:07,875 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 63. [2022-04-05 08:25:07,876 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 39 states have (on average 1.2307692307692308) internal successors, (48), 41 states have internal predecessors, (48), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-05 08:25:07,876 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 76 transitions. [2022-04-05 08:25:07,877 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 76 transitions. Word has length 30 [2022-04-05 08:25:07,877 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:25:07,877 INFO L478 AbstractCegarLoop]: Abstraction has 63 states and 76 transitions. [2022-04-05 08:25:07,877 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 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-04-05 08:25:07,877 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 76 transitions. [2022-04-05 08:25:07,878 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2022-04-05 08:25:07,878 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:25:07,878 INFO L499 BasicCegarLoop]: trace histogram [5, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:25:07,901 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-04-05 08:25:08,078 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:25:08,079 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:25:08,079 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:25:08,079 INFO L85 PathProgramCache]: Analyzing trace with hash 1811137592, now seen corresponding path program 1 times [2022-04-05 08:25:08,080 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:25:08,080 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2069414690] [2022-04-05 08:25:08,080 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:25:08,080 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:25:08,091 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 08:25:08,092 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [584409799] [2022-04-05 08:25:08,092 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:25:08,092 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:25:08,092 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 08:25:08,093 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-04-05 08:25:08,094 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-04-05 08:25:08,132 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:25:08,133 INFO L263 TraceCheckSpWp]: Trace formula consists of 126 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-05 08:25:08,134 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 08:25:08,208 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 18 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2022-04-05 08:25:08,208 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 08:25:08,315 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-04-05 08:25:08,316 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:25:08,316 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2069414690] [2022-04-05 08:25:08,316 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 08:25:08,316 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [584409799] [2022-04-05 08:25:08,316 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [584409799] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 08:25:08,316 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 08:25:08,316 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2022-04-05 08:25:08,317 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [471045146] [2022-04-05 08:25:08,317 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 08:25:08,317 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-04-05 08:25:08,317 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:25:08,317 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-04-05 08:25:08,318 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2022-04-05 08:25:08,318 INFO L87 Difference]: Start difference. First operand 63 states and 76 transitions. Second operand has 8 states, 8 states have (on average 3.625) internal successors, (29), 8 states have internal predecessors, (29), 6 states have call successors, (12), 5 states have call predecessors, (12), 5 states have return successors, (10), 5 states have call predecessors, (10), 4 states have call successors, (10) [2022-04-05 08:25:08,403 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:25:08,403 INFO L93 Difference]: Finished difference Result 144 states and 177 transitions. [2022-04-05 08:25:08,404 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-04-05 08:25:08,404 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), 6 states have call successors, (12), 5 states have call predecessors, (12), 5 states have return successors, (10), 5 states have call predecessors, (10), 4 states have call successors, (10) Word has length 37 [2022-04-05 08:25:08,405 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:25:08,408 INFO L225 Difference]: With dead ends: 144 [2022-04-05 08:25:08,408 INFO L226 Difference]: Without dead ends: 119 [2022-04-05 08:25:08,409 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 67 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-04-05 08:25:08,409 INFO L913 BasicCegarLoop]: 45 mSDtfsCounter, 41 mSDsluCounter, 162 mSDsCounter, 0 mSdLazyCounter, 57 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 207 SdHoareTripleChecker+Invalid, 71 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 57 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-05 08:25:08,410 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [41 Valid, 207 Invalid, 71 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 57 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-05 08:25:08,411 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 119 states. [2022-04-05 08:25:08,425 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 119 to 112. [2022-04-05 08:25:08,426 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 112 states, 71 states have (on average 1.2112676056338028) internal successors, (86), 74 states have internal predecessors, (86), 25 states have call successors, (25), 16 states have call predecessors, (25), 15 states have return successors, (22), 21 states have call predecessors, (22), 22 states have call successors, (22) [2022-04-05 08:25:08,429 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 112 states to 112 states and 133 transitions. [2022-04-05 08:25:08,429 INFO L78 Accepts]: Start accepts. Automaton has 112 states and 133 transitions. Word has length 37 [2022-04-05 08:25:08,429 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:25:08,429 INFO L478 AbstractCegarLoop]: Abstraction has 112 states and 133 transitions. [2022-04-05 08:25:08,429 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), 6 states have call successors, (12), 5 states have call predecessors, (12), 5 states have return successors, (10), 5 states have call predecessors, (10), 4 states have call successors, (10) [2022-04-05 08:25:08,430 INFO L276 IsEmpty]: Start isEmpty. Operand 112 states and 133 transitions. [2022-04-05 08:25:08,430 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2022-04-05 08:25:08,430 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:25:08,430 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:25:08,448 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-04-05 08:25:08,634 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:25:08,635 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:25:08,635 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:25:08,635 INFO L85 PathProgramCache]: Analyzing trace with hash -599722260, now seen corresponding path program 1 times [2022-04-05 08:25:08,635 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:25:08,635 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [635848794] [2022-04-05 08:25:08,635 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:25:08,635 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:25:08,643 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 08:25:08,643 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1025296300] [2022-04-05 08:25:08,643 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:25:08,643 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:25:08,643 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 08:25:08,644 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-04-05 08:25:08,655 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-04-05 08:25:08,689 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:25:08,690 INFO L263 TraceCheckSpWp]: Trace formula consists of 130 conjuncts, 13 conjunts are in the unsatisfiable core [2022-04-05 08:25:08,692 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 08:25:08,840 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 5 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-04-05 08:25:08,841 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 08:25:08,956 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-04-05 08:25:08,957 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:25:08,957 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [635848794] [2022-04-05 08:25:08,957 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 08:25:08,957 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1025296300] [2022-04-05 08:25:08,957 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1025296300] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-05 08:25:08,957 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-05 08:25:08,957 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2022-04-05 08:25:08,957 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [283275290] [2022-04-05 08:25:08,957 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 08:25:08,958 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-05 08:25:08,958 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:25:08,958 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-05 08:25:08,958 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-04-05 08:25:08,959 INFO L87 Difference]: Start difference. First operand 112 states and 133 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 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-04-05 08:25:09,009 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:25:09,009 INFO L93 Difference]: Finished difference Result 129 states and 154 transitions. [2022-04-05 08:25:09,009 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-05 08:25:09,009 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 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 40 [2022-04-05 08:25:09,010 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:25:09,011 INFO L225 Difference]: With dead ends: 129 [2022-04-05 08:25:09,011 INFO L226 Difference]: Without dead ends: 125 [2022-04-05 08:25:09,011 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 80 GetRequests, 72 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2022-04-05 08:25:09,012 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 11 mSDsluCounter, 69 mSDsCounter, 0 mSdLazyCounter, 46 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 103 SdHoareTripleChecker+Invalid, 47 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 46 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-05 08:25:09,012 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 103 Invalid, 47 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 46 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-05 08:25:09,012 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 125 states. [2022-04-05 08:25:09,023 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 125 to 122. [2022-04-05 08:25:09,023 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 122 states, 78 states have (on average 1.1794871794871795) internal successors, (92), 81 states have internal predecessors, (92), 27 states have call successors, (27), 18 states have call predecessors, (27), 16 states have return successors, (24), 22 states have call predecessors, (24), 24 states have call successors, (24) [2022-04-05 08:25:09,024 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 122 states to 122 states and 143 transitions. [2022-04-05 08:25:09,024 INFO L78 Accepts]: Start accepts. Automaton has 122 states and 143 transitions. Word has length 40 [2022-04-05 08:25:09,024 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:25:09,024 INFO L478 AbstractCegarLoop]: Abstraction has 122 states and 143 transitions. [2022-04-05 08:25:09,024 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 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-04-05 08:25:09,025 INFO L276 IsEmpty]: Start isEmpty. Operand 122 states and 143 transitions. [2022-04-05 08:25:09,026 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 54 [2022-04-05 08:25:09,026 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:25:09,026 INFO L499 BasicCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:25:09,050 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-04-05 08:25:09,242 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:25:09,243 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:25:09,243 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:25:09,243 INFO L85 PathProgramCache]: Analyzing trace with hash 560903707, now seen corresponding path program 1 times [2022-04-05 08:25:09,244 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:25:09,244 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [150788983] [2022-04-05 08:25:09,244 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:25:09,244 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:25:09,252 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 08:25:09,252 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1095189732] [2022-04-05 08:25:09,252 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:25:09,252 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:25:09,252 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 08:25:09,253 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-04-05 08:25:09,282 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-04-05 08:25:09,310 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:25:09,311 INFO L263 TraceCheckSpWp]: Trace formula consists of 154 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-05 08:25:09,313 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 08:25:09,420 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 36 proven. 42 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2022-04-05 08:25:09,420 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 08:25:09,529 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 14 proven. 6 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2022-04-05 08:25:09,529 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:25:09,529 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [150788983] [2022-04-05 08:25:09,529 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 08:25:09,529 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1095189732] [2022-04-05 08:25:09,529 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1095189732] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 08:25:09,529 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 08:25:09,529 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2022-04-05 08:25:09,530 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1131604714] [2022-04-05 08:25:09,530 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 08:25:09,530 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-04-05 08:25:09,530 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:25:09,531 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-04-05 08:25:09,531 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2022-04-05 08:25:09,531 INFO L87 Difference]: Start difference. First operand 122 states and 143 transitions. Second operand has 10 states, 10 states have (on average 3.6) internal successors, (36), 10 states have internal predecessors, (36), 8 states have call successors, (18), 6 states have call predecessors, (18), 6 states have return successors, (16), 7 states have call predecessors, (16), 6 states have call successors, (16) [2022-04-05 08:25:09,665 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:25:09,666 INFO L93 Difference]: Finished difference Result 245 states and 298 transitions. [2022-04-05 08:25:09,681 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-04-05 08:25:09,681 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.6) internal successors, (36), 10 states have internal predecessors, (36), 8 states have call successors, (18), 6 states have call predecessors, (18), 6 states have return successors, (16), 7 states have call predecessors, (16), 6 states have call successors, (16) Word has length 53 [2022-04-05 08:25:09,682 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:25:09,683 INFO L225 Difference]: With dead ends: 245 [2022-04-05 08:25:09,683 INFO L226 Difference]: Without dead ends: 224 [2022-04-05 08:25:09,684 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 108 GetRequests, 97 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=52, Invalid=104, Unknown=0, NotChecked=0, Total=156 [2022-04-05 08:25:09,684 INFO L913 BasicCegarLoop]: 59 mSDtfsCounter, 80 mSDsluCounter, 243 mSDsCounter, 0 mSdLazyCounter, 119 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 80 SdHoareTripleChecker+Valid, 302 SdHoareTripleChecker+Invalid, 143 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 119 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 08:25:09,684 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [80 Valid, 302 Invalid, 143 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 119 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 08:25:09,685 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 224 states. [2022-04-05 08:25:09,702 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 224 to 217. [2022-04-05 08:25:09,703 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 217 states, 139 states have (on average 1.1942446043165467) internal successors, (166), 148 states have internal predecessors, (166), 51 states have call successors, (51), 28 states have call predecessors, (51), 26 states have return successors, (46), 40 states have call predecessors, (46), 46 states have call successors, (46) [2022-04-05 08:25:09,704 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 217 states to 217 states and 263 transitions. [2022-04-05 08:25:09,704 INFO L78 Accepts]: Start accepts. Automaton has 217 states and 263 transitions. Word has length 53 [2022-04-05 08:25:09,705 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:25:09,705 INFO L478 AbstractCegarLoop]: Abstraction has 217 states and 263 transitions. [2022-04-05 08:25:09,705 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.6) internal successors, (36), 10 states have internal predecessors, (36), 8 states have call successors, (18), 6 states have call predecessors, (18), 6 states have return successors, (16), 7 states have call predecessors, (16), 6 states have call successors, (16) [2022-04-05 08:25:09,705 INFO L276 IsEmpty]: Start isEmpty. Operand 217 states and 263 transitions. [2022-04-05 08:25:09,706 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2022-04-05 08:25:09,706 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:25:09,707 INFO L499 BasicCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:25:09,732 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-04-05 08:25:09,923 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:25:09,923 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:25:09,924 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:25:09,924 INFO L85 PathProgramCache]: Analyzing trace with hash -453219492, now seen corresponding path program 1 times [2022-04-05 08:25:09,924 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:25:09,924 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [490354643] [2022-04-05 08:25:09,924 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:25:09,924 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:25:09,933 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 08:25:09,933 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [508798326] [2022-04-05 08:25:09,933 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:25:09,933 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:25:09,933 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 08:25:09,934 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-04-05 08:25:09,947 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-04-05 08:25:09,983 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:25:09,984 INFO L263 TraceCheckSpWp]: Trace formula consists of 178 conjuncts, 25 conjunts are in the unsatisfiable core [2022-04-05 08:25:09,987 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 08:25:10,322 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 16 proven. 9 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2022-04-05 08:25:10,323 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 08:25:11,323 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 16 proven. 9 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2022-04-05 08:25:11,324 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:25:11,324 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [490354643] [2022-04-05 08:25:11,324 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 08:25:11,324 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [508798326] [2022-04-05 08:25:11,324 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [508798326] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 08:25:11,324 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 08:25:11,324 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2022-04-05 08:25:11,324 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [219248296] [2022-04-05 08:25:11,325 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 08:25:11,325 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-04-05 08:25:11,325 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:25:11,325 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-04-05 08:25:11,326 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2022-04-05 08:25:11,326 INFO L87 Difference]: Start difference. First operand 217 states and 263 transitions. Second operand has 10 states, 10 states have (on average 3.4) internal successors, (34), 9 states have internal predecessors, (34), 7 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (17), 5 states have call predecessors, (17), 5 states have call successors, (17) [2022-04-05 08:25:15,803 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:25:15,804 INFO L93 Difference]: Finished difference Result 371 states and 479 transitions. [2022-04-05 08:25:15,804 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-04-05 08:25:15,804 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.4) internal successors, (34), 9 states have internal predecessors, (34), 7 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (17), 5 states have call predecessors, (17), 5 states have call successors, (17) Word has length 62 [2022-04-05 08:25:15,805 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:25:15,809 INFO L225 Difference]: With dead ends: 371 [2022-04-05 08:25:15,809 INFO L226 Difference]: Without dead ends: 303 [2022-04-05 08:25:15,811 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 127 GetRequests, 112 SyntacticMatches, 3 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 3.9s TimeCoverageRelationStatistics Valid=50, Invalid=132, Unknown=0, NotChecked=0, Total=182 [2022-04-05 08:25:15,812 INFO L913 BasicCegarLoop]: 51 mSDtfsCounter, 49 mSDsluCounter, 153 mSDsCounter, 0 mSdLazyCounter, 308 mSolverCounterSat, 68 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 55 SdHoareTripleChecker+Valid, 204 SdHoareTripleChecker+Invalid, 376 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 68 IncrementalHoareTripleChecker+Valid, 308 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2022-04-05 08:25:15,812 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [55 Valid, 204 Invalid, 376 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [68 Valid, 308 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2022-04-05 08:25:15,813 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 303 states. [2022-04-05 08:25:15,851 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 303 to 274. [2022-04-05 08:25:15,853 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 274 states, 185 states have (on average 1.2324324324324325) internal successors, (228), 191 states have internal predecessors, (228), 58 states have call successors, (58), 31 states have call predecessors, (58), 30 states have return successors, (55), 51 states have call predecessors, (55), 55 states have call successors, (55) [2022-04-05 08:25:15,855 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 274 states to 274 states and 341 transitions. [2022-04-05 08:25:15,855 INFO L78 Accepts]: Start accepts. Automaton has 274 states and 341 transitions. Word has length 62 [2022-04-05 08:25:15,856 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:25:15,856 INFO L478 AbstractCegarLoop]: Abstraction has 274 states and 341 transitions. [2022-04-05 08:25:15,856 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.4) internal successors, (34), 9 states have internal predecessors, (34), 7 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (17), 5 states have call predecessors, (17), 5 states have call successors, (17) [2022-04-05 08:25:15,857 INFO L276 IsEmpty]: Start isEmpty. Operand 274 states and 341 transitions. [2022-04-05 08:25:15,864 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2022-04-05 08:25:15,864 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:25:15,865 INFO L499 BasicCegarLoop]: trace histogram [11, 10, 10, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:25:15,890 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-04-05 08:25:16,078 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:25:16,078 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:25:16,079 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:25:16,079 INFO L85 PathProgramCache]: Analyzing trace with hash 929445032, now seen corresponding path program 1 times [2022-04-05 08:25:16,079 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:25:16,079 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1561960195] [2022-04-05 08:25:16,079 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:25:16,080 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:25:16,087 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 08:25:16,096 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [914778751] [2022-04-05 08:25:16,097 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:25:16,097 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:25:16,097 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 08:25:16,098 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-04-05 08:25:16,118 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-04-05 08:25:16,147 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:25:16,149 INFO L263 TraceCheckSpWp]: Trace formula consists of 198 conjuncts, 35 conjunts are in the unsatisfiable core [2022-04-05 08:25:16,151 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 08:25:16,621 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 66 proven. 13 refuted. 0 times theorem prover too weak. 132 trivial. 0 not checked. [2022-04-05 08:25:16,621 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 08:25:16,871 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 68 proven. 2 refuted. 0 times theorem prover too weak. 141 trivial. 0 not checked. [2022-04-05 08:25:16,871 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:25:16,871 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1561960195] [2022-04-05 08:25:16,871 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 08:25:16,871 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [914778751] [2022-04-05 08:25:16,871 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [914778751] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 08:25:16,871 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 08:25:16,872 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 9] total 16 [2022-04-05 08:25:16,872 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [872370789] [2022-04-05 08:25:16,872 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 08:25:16,873 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-04-05 08:25:16,873 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:25:16,873 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-04-05 08:25:16,873 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=189, Unknown=0, NotChecked=0, Total=240 [2022-04-05 08:25:16,874 INFO L87 Difference]: Start difference. First operand 274 states and 341 transitions. Second operand has 16 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 11 states have internal predecessors, (37), 8 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) [2022-04-05 08:25:17,322 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:25:17,322 INFO L93 Difference]: Finished difference Result 335 states and 416 transitions. [2022-04-05 08:25:17,325 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-04-05 08:25:17,325 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 11 states have internal predecessors, (37), 8 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) Word has length 73 [2022-04-05 08:25:17,325 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:25:17,327 INFO L225 Difference]: With dead ends: 335 [2022-04-05 08:25:17,327 INFO L226 Difference]: Without dead ends: 239 [2022-04-05 08:25:17,327 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 149 GetRequests, 129 SyntacticMatches, 2 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 39 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=76, Invalid=304, Unknown=0, NotChecked=0, Total=380 [2022-04-05 08:25:17,328 INFO L913 BasicCegarLoop]: 35 mSDtfsCounter, 54 mSDsluCounter, 159 mSDsCounter, 0 mSdLazyCounter, 434 mSolverCounterSat, 69 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 68 SdHoareTripleChecker+Valid, 194 SdHoareTripleChecker+Invalid, 503 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 69 IncrementalHoareTripleChecker+Valid, 434 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-04-05 08:25:17,328 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [68 Valid, 194 Invalid, 503 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [69 Valid, 434 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2022-04-05 08:25:17,329 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 239 states. [2022-04-05 08:25:17,347 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 239 to 223. [2022-04-05 08:25:17,347 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 223 states, 150 states have (on average 1.1933333333333334) internal successors, (179), 154 states have internal predecessors, (179), 45 states have call successors, (45), 29 states have call predecessors, (45), 27 states have return successors, (42), 39 states have call predecessors, (42), 42 states have call successors, (42) [2022-04-05 08:25:17,350 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 223 states to 223 states and 266 transitions. [2022-04-05 08:25:17,350 INFO L78 Accepts]: Start accepts. Automaton has 223 states and 266 transitions. Word has length 73 [2022-04-05 08:25:17,350 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:25:17,350 INFO L478 AbstractCegarLoop]: Abstraction has 223 states and 266 transitions. [2022-04-05 08:25:17,351 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 11 states have internal predecessors, (37), 8 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) [2022-04-05 08:25:17,351 INFO L276 IsEmpty]: Start isEmpty. Operand 223 states and 266 transitions. [2022-04-05 08:25:17,353 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 83 [2022-04-05 08:25:17,353 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:25:17,353 INFO L499 BasicCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:25:17,379 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-04-05 08:25:17,567 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,SelfDestructingSolverStorable11 [2022-04-05 08:25:17,568 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:25:17,568 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:25:17,568 INFO L85 PathProgramCache]: Analyzing trace with hash -1139963303, now seen corresponding path program 1 times [2022-04-05 08:25:17,568 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:25:17,568 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [130171427] [2022-04-05 08:25:17,568 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:25:17,568 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:25:17,574 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 08:25:17,574 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [697460239] [2022-04-05 08:25:17,574 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:25:17,574 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:25:17,574 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 08:25:17,575 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-04-05 08:25:17,579 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2022-04-05 08:25:17,622 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:25:17,623 INFO L263 TraceCheckSpWp]: Trace formula consists of 211 conjuncts, 4 conjunts are in the unsatisfiable core [2022-04-05 08:25:17,627 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 08:25:17,808 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 84 proven. 0 refuted. 0 times theorem prover too weak. 222 trivial. 0 not checked. [2022-04-05 08:25:17,808 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-05 08:25:17,808 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:25:17,808 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [130171427] [2022-04-05 08:25:17,809 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 08:25:17,809 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [697460239] [2022-04-05 08:25:17,809 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [697460239] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 08:25:17,809 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 08:25:17,809 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-05 08:25:17,809 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [938417190] [2022-04-05 08:25:17,809 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 08:25:17,809 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-05 08:25:17,809 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:25:17,810 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-05 08:25:17,810 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2022-04-05 08:25:17,810 INFO L87 Difference]: Start difference. First operand 223 states and 266 transitions. Second operand has 5 states, 5 states have (on average 4.6) internal successors, (23), 5 states have internal predecessors, (23), 5 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2022-04-05 08:25:17,874 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:25:17,874 INFO L93 Difference]: Finished difference Result 242 states and 289 transitions. [2022-04-05 08:25:17,874 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-05 08:25:17,875 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.6) internal successors, (23), 5 states have internal predecessors, (23), 5 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) Word has length 82 [2022-04-05 08:25:17,875 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:25:17,876 INFO L225 Difference]: With dead ends: 242 [2022-04-05 08:25:17,876 INFO L226 Difference]: Without dead ends: 222 [2022-04-05 08:25:17,877 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 78 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2022-04-05 08:25:17,878 INFO L913 BasicCegarLoop]: 57 mSDtfsCounter, 24 mSDsluCounter, 56 mSDsCounter, 0 mSdLazyCounter, 41 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 113 SdHoareTripleChecker+Invalid, 54 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 41 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-05 08:25:17,878 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [31 Valid, 113 Invalid, 54 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-05 08:25:17,879 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 222 states. [2022-04-05 08:25:17,915 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 222 to 217. [2022-04-05 08:25:17,916 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 217 states, 147 states have (on average 1.163265306122449) internal successors, (171), 149 states have internal predecessors, (171), 43 states have call successors, (43), 27 states have call predecessors, (43), 26 states have return successors, (41), 40 states have call predecessors, (41), 41 states have call successors, (41) [2022-04-05 08:25:17,917 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 217 states to 217 states and 255 transitions. [2022-04-05 08:25:17,917 INFO L78 Accepts]: Start accepts. Automaton has 217 states and 255 transitions. Word has length 82 [2022-04-05 08:25:17,918 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:25:17,918 INFO L478 AbstractCegarLoop]: Abstraction has 217 states and 255 transitions. [2022-04-05 08:25:17,919 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.6) internal successors, (23), 5 states have internal predecessors, (23), 5 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2022-04-05 08:25:17,919 INFO L276 IsEmpty]: Start isEmpty. Operand 217 states and 255 transitions. [2022-04-05 08:25:17,920 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 95 [2022-04-05 08:25:17,920 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:25:17,920 INFO L499 BasicCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:25:17,945 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2022-04-05 08:25:18,134 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2022-04-05 08:25:18,134 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:25:18,135 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:25:18,135 INFO L85 PathProgramCache]: Analyzing trace with hash -2090333941, now seen corresponding path program 2 times [2022-04-05 08:25:18,135 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:25:18,135 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [286758277] [2022-04-05 08:25:18,135 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:25:18,135 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:25:18,156 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 08:25:18,157 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [206584838] [2022-04-05 08:25:18,157 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-05 08:25:18,157 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:25:18,157 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 08:25:18,160 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 08:25:18,183 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2022-04-05 08:25:18,225 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-05 08:25:18,225 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 08:25:18,227 INFO L263 TraceCheckSpWp]: Trace formula consists of 248 conjuncts, 39 conjunts are in the unsatisfiable core [2022-04-05 08:25:18,229 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 08:25:18,848 INFO L134 CoverageAnalysis]: Checked inductivity of 368 backedges. 26 proven. 30 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2022-04-05 08:25:18,848 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 08:25:34,474 INFO L134 CoverageAnalysis]: Checked inductivity of 368 backedges. 26 proven. 30 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2022-04-05 08:25:34,474 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:25:34,474 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [286758277] [2022-04-05 08:25:34,474 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 08:25:34,474 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [206584838] [2022-04-05 08:25:34,475 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [206584838] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 08:25:34,475 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 08:25:34,475 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 16 [2022-04-05 08:25:34,475 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1086439522] [2022-04-05 08:25:34,475 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 08:25:34,475 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-04-05 08:25:34,475 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:25:34,476 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-04-05 08:25:34,476 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=180, Unknown=0, NotChecked=0, Total=240 [2022-04-05 08:25:34,476 INFO L87 Difference]: Start difference. First operand 217 states and 255 transitions. Second operand has 16 states, 16 states have (on average 3.0) internal successors, (48), 15 states have internal predecessors, (48), 11 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (27), 9 states have call predecessors, (27), 9 states have call successors, (27) [2022-04-05 08:25:47,454 WARN L232 SmtUtils]: Spent 12.32s on a formula simplification. DAG size of input: 192 DAG size of output: 86 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-05 08:25:50,065 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-04-05 08:25:51,700 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.05s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 08:25:58,925 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.76s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 08:26:00,937 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-04-05 08:26:03,003 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-04-05 08:26:10,705 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-04-05 08:26:12,380 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:26:12,380 INFO L93 Difference]: Finished difference Result 332 states and 434 transitions. [2022-04-05 08:26:12,381 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-04-05 08:26:12,381 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 3.0) internal successors, (48), 15 states have internal predecessors, (48), 11 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (27), 9 states have call predecessors, (27), 9 states have call successors, (27) Word has length 94 [2022-04-05 08:26:12,381 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:26:12,382 INFO L225 Difference]: With dead ends: 332 [2022-04-05 08:26:12,382 INFO L226 Difference]: Without dead ends: 275 [2022-04-05 08:26:12,383 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 193 GetRequests, 170 SyntacticMatches, 3 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 22.3s TimeCoverageRelationStatistics Valid=126, Invalid=335, Unknown=1, NotChecked=0, Total=462 [2022-04-05 08:26:12,383 INFO L913 BasicCegarLoop]: 73 mSDtfsCounter, 127 mSDsluCounter, 308 mSDsCounter, 0 mSdLazyCounter, 799 mSolverCounterSat, 180 mSolverCounterUnsat, 4 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 17.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 138 SdHoareTripleChecker+Valid, 381 SdHoareTripleChecker+Invalid, 983 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 180 IncrementalHoareTripleChecker+Valid, 799 IncrementalHoareTripleChecker+Invalid, 4 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 17.7s IncrementalHoareTripleChecker+Time [2022-04-05 08:26:12,384 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [138 Valid, 381 Invalid, 983 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [180 Valid, 799 Invalid, 4 Unknown, 0 Unchecked, 17.7s Time] [2022-04-05 08:26:12,384 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 275 states. [2022-04-05 08:26:12,409 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 275 to 257. [2022-04-05 08:26:12,409 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 257 states, 172 states have (on average 1.2267441860465116) internal successors, (211), 177 states have internal predecessors, (211), 57 states have call successors, (57), 28 states have call predecessors, (57), 27 states have return successors, (55), 51 states have call predecessors, (55), 55 states have call successors, (55) [2022-04-05 08:26:12,411 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 257 states to 257 states and 323 transitions. [2022-04-05 08:26:12,411 INFO L78 Accepts]: Start accepts. Automaton has 257 states and 323 transitions. Word has length 94 [2022-04-05 08:26:12,411 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:26:12,411 INFO L478 AbstractCegarLoop]: Abstraction has 257 states and 323 transitions. [2022-04-05 08:26:12,412 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 3.0) internal successors, (48), 15 states have internal predecessors, (48), 11 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (27), 9 states have call predecessors, (27), 9 states have call successors, (27) [2022-04-05 08:26:12,412 INFO L276 IsEmpty]: Start isEmpty. Operand 257 states and 323 transitions. [2022-04-05 08:26:12,413 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 101 [2022-04-05 08:26:12,413 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:26:12,413 INFO L499 BasicCegarLoop]: trace histogram [15, 14, 14, 5, 4, 4, 4, 4, 4, 4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:26:12,438 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2022-04-05 08:26:12,627 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2022-04-05 08:26:12,627 INFO L403 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:26:12,628 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:26:12,628 INFO L85 PathProgramCache]: Analyzing trace with hash -105290329, now seen corresponding path program 1 times [2022-04-05 08:26:12,628 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:26:12,628 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [6052833] [2022-04-05 08:26:12,628 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:26:12,628 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:26:12,635 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 08:26:12,635 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [983147505] [2022-04-05 08:26:12,635 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:26:12,635 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:26:12,635 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 08:26:12,637 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 08:26:12,639 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2022-04-05 08:26:12,692 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:26:12,693 INFO L263 TraceCheckSpWp]: Trace formula consists of 261 conjuncts, 13 conjunts are in the unsatisfiable core [2022-04-05 08:26:12,695 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 08:26:12,892 INFO L134 CoverageAnalysis]: Checked inductivity of 438 backedges. 120 proven. 260 refuted. 0 times theorem prover too weak. 58 trivial. 0 not checked. [2022-04-05 08:26:12,893 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 08:26:13,076 INFO L134 CoverageAnalysis]: Checked inductivity of 438 backedges. 28 proven. 44 refuted. 0 times theorem prover too weak. 366 trivial. 0 not checked. [2022-04-05 08:26:13,076 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:26:13,076 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [6052833] [2022-04-05 08:26:13,076 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 08:26:13,077 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [983147505] [2022-04-05 08:26:13,077 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [983147505] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 08:26:13,077 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 08:26:13,077 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2022-04-05 08:26:13,077 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [448337254] [2022-04-05 08:26:13,077 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 08:26:13,077 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-04-05 08:26:13,078 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:26:13,078 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-04-05 08:26:13,078 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2022-04-05 08:26:13,078 INFO L87 Difference]: Start difference. First operand 257 states and 323 transitions. Second operand has 14 states, 14 states have (on average 4.214285714285714) internal successors, (59), 14 states have internal predecessors, (59), 12 states have call successors, (32), 8 states have call predecessors, (32), 8 states have return successors, (30), 11 states have call predecessors, (30), 10 states have call successors, (30) [2022-04-05 08:26:13,382 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:26:13,382 INFO L93 Difference]: Finished difference Result 746 states and 1016 transitions. [2022-04-05 08:26:13,382 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2022-04-05 08:26:13,383 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 4.214285714285714) internal successors, (59), 14 states have internal predecessors, (59), 12 states have call successors, (32), 8 states have call predecessors, (32), 8 states have return successors, (30), 11 states have call predecessors, (30), 10 states have call successors, (30) Word has length 100 [2022-04-05 08:26:13,383 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:26:13,386 INFO L225 Difference]: With dead ends: 746 [2022-04-05 08:26:13,386 INFO L226 Difference]: Without dead ends: 659 [2022-04-05 08:26:13,387 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 208 GetRequests, 187 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 55 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=184, Invalid=322, Unknown=0, NotChecked=0, Total=506 [2022-04-05 08:26:13,387 INFO L913 BasicCegarLoop]: 80 mSDtfsCounter, 178 mSDsluCounter, 214 mSDsCounter, 0 mSdLazyCounter, 159 mSolverCounterSat, 87 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 178 SdHoareTripleChecker+Valid, 294 SdHoareTripleChecker+Invalid, 246 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 87 IncrementalHoareTripleChecker+Valid, 159 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-05 08:26:13,388 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [178 Valid, 294 Invalid, 246 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [87 Valid, 159 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-05 08:26:13,388 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 659 states. [2022-04-05 08:26:13,448 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 659 to 552. [2022-04-05 08:26:13,449 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 552 states, 361 states have (on average 1.2825484764542936) internal successors, (463), 378 states have internal predecessors, (463), 136 states have call successors, (136), 56 states have call predecessors, (136), 54 states have return successors, (131), 117 states have call predecessors, (131), 131 states have call successors, (131) [2022-04-05 08:26:13,452 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 552 states to 552 states and 730 transitions. [2022-04-05 08:26:13,452 INFO L78 Accepts]: Start accepts. Automaton has 552 states and 730 transitions. Word has length 100 [2022-04-05 08:26:13,452 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:26:13,452 INFO L478 AbstractCegarLoop]: Abstraction has 552 states and 730 transitions. [2022-04-05 08:26:13,452 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 4.214285714285714) internal successors, (59), 14 states have internal predecessors, (59), 12 states have call successors, (32), 8 states have call predecessors, (32), 8 states have return successors, (30), 11 states have call predecessors, (30), 10 states have call successors, (30) [2022-04-05 08:26:13,453 INFO L276 IsEmpty]: Start isEmpty. Operand 552 states and 730 transitions. [2022-04-05 08:26:13,454 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 109 [2022-04-05 08:26:13,454 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:26:13,454 INFO L499 BasicCegarLoop]: trace histogram [16, 15, 15, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:26:13,472 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2022-04-05 08:26:13,661 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2022-04-05 08:26:13,661 INFO L403 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:26:13,661 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:26:13,661 INFO L85 PathProgramCache]: Analyzing trace with hash 331614142, now seen corresponding path program 1 times [2022-04-05 08:26:13,662 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:26:13,662 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [262207233] [2022-04-05 08:26:13,662 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:26:13,662 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:26:13,669 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 08:26:13,669 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1997366695] [2022-04-05 08:26:13,669 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:26:13,669 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:26:13,670 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 08:26:13,670 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 08:26:13,683 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2022-04-05 08:26:13,736 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:26:13,737 INFO L263 TraceCheckSpWp]: Trace formula consists of 281 conjuncts, 17 conjunts are in the unsatisfiable core [2022-04-05 08:26:13,740 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 08:26:13,922 INFO L134 CoverageAnalysis]: Checked inductivity of 492 backedges. 30 proven. 414 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2022-04-05 08:26:13,922 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 08:26:14,143 INFO L134 CoverageAnalysis]: Checked inductivity of 492 backedges. 30 proven. 42 refuted. 0 times theorem prover too weak. 420 trivial. 0 not checked. [2022-04-05 08:26:14,144 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:26:14,144 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [262207233] [2022-04-05 08:26:14,144 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 08:26:14,144 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1997366695] [2022-04-05 08:26:14,144 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1997366695] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 08:26:14,144 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 08:26:14,144 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 18 [2022-04-05 08:26:14,144 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1412425878] [2022-04-05 08:26:14,144 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 08:26:14,145 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2022-04-05 08:26:14,145 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:26:14,145 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2022-04-05 08:26:14,146 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=125, Invalid=181, Unknown=0, NotChecked=0, Total=306 [2022-04-05 08:26:14,146 INFO L87 Difference]: Start difference. First operand 552 states and 730 transitions. Second operand has 18 states, 18 states have (on average 4.222222222222222) internal successors, (76), 18 states have internal predecessors, (76), 16 states have call successors, (34), 10 states have call predecessors, (34), 9 states have return successors, (32), 14 states have call predecessors, (32), 13 states have call successors, (32) [2022-04-05 08:26:14,656 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:26:14,657 INFO L93 Difference]: Finished difference Result 1159 states and 1613 transitions. [2022-04-05 08:26:14,657 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2022-04-05 08:26:14,657 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 4.222222222222222) internal successors, (76), 18 states have internal predecessors, (76), 16 states have call successors, (34), 10 states have call predecessors, (34), 9 states have return successors, (32), 14 states have call predecessors, (32), 13 states have call successors, (32) Word has length 108 [2022-04-05 08:26:14,658 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:26:14,662 INFO L225 Difference]: With dead ends: 1159 [2022-04-05 08:26:14,662 INFO L226 Difference]: Without dead ends: 1122 [2022-04-05 08:26:14,663 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 225 GetRequests, 199 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 79 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=259, Invalid=497, Unknown=0, NotChecked=0, Total=756 [2022-04-05 08:26:14,663 INFO L913 BasicCegarLoop]: 100 mSDtfsCounter, 324 mSDsluCounter, 395 mSDsCounter, 0 mSdLazyCounter, 273 mSolverCounterSat, 219 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 324 SdHoareTripleChecker+Valid, 495 SdHoareTripleChecker+Invalid, 492 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 219 IncrementalHoareTripleChecker+Valid, 273 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-04-05 08:26:14,664 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [324 Valid, 495 Invalid, 492 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [219 Valid, 273 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-04-05 08:26:14,665 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1122 states. [2022-04-05 08:26:14,763 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1122 to 1097. [2022-04-05 08:26:14,765 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1097 states, 729 states have (on average 1.2455418381344308) internal successors, (908), 758 states have internal predecessors, (908), 279 states have call successors, (279), 90 states have call predecessors, (279), 88 states have return successors, (270), 248 states have call predecessors, (270), 270 states have call successors, (270) [2022-04-05 08:26:14,772 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1097 states to 1097 states and 1457 transitions. [2022-04-05 08:26:14,772 INFO L78 Accepts]: Start accepts. Automaton has 1097 states and 1457 transitions. Word has length 108 [2022-04-05 08:26:14,772 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:26:14,772 INFO L478 AbstractCegarLoop]: Abstraction has 1097 states and 1457 transitions. [2022-04-05 08:26:14,773 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 4.222222222222222) internal successors, (76), 18 states have internal predecessors, (76), 16 states have call successors, (34), 10 states have call predecessors, (34), 9 states have return successors, (32), 14 states have call predecessors, (32), 13 states have call successors, (32) [2022-04-05 08:26:14,773 INFO L276 IsEmpty]: Start isEmpty. Operand 1097 states and 1457 transitions. [2022-04-05 08:26:14,774 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 111 [2022-04-05 08:26:14,774 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:26:14,774 INFO L499 BasicCegarLoop]: trace histogram [17, 16, 16, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:26:14,800 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2022-04-05 08:26:14,988 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2022-04-05 08:26:14,988 INFO L403 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:26:14,988 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:26:14,988 INFO L85 PathProgramCache]: Analyzing trace with hash 1288142005, now seen corresponding path program 1 times [2022-04-05 08:26:14,988 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:26:14,989 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [430664310] [2022-04-05 08:26:14,989 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:26:14,989 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:26:14,998 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 08:26:14,998 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [436743341] [2022-04-05 08:26:14,998 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:26:14,998 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:26:14,999 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 08:26:14,999 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 08:26:15,001 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2022-04-05 08:26:15,051 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:26:15,053 INFO L263 TraceCheckSpWp]: Trace formula consists of 277 conjuncts, 14 conjunts are in the unsatisfiable core [2022-04-05 08:26:15,055 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 08:26:15,315 INFO L134 CoverageAnalysis]: Checked inductivity of 546 backedges. 32 proven. 34 refuted. 0 times theorem prover too weak. 480 trivial. 0 not checked. [2022-04-05 08:26:15,315 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 08:26:16,119 INFO L134 CoverageAnalysis]: Checked inductivity of 546 backedges. 32 proven. 34 refuted. 0 times theorem prover too weak. 480 trivial. 0 not checked. [2022-04-05 08:26:16,120 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:26:16,120 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [430664310] [2022-04-05 08:26:16,120 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 08:26:16,120 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [436743341] [2022-04-05 08:26:16,120 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [436743341] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 08:26:16,120 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 08:26:16,120 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2022-04-05 08:26:16,120 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1838736318] [2022-04-05 08:26:16,120 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 08:26:16,120 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-04-05 08:26:16,121 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:26:16,121 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-04-05 08:26:16,121 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2022-04-05 08:26:16,121 INFO L87 Difference]: Start difference. First operand 1097 states and 1457 transitions. Second operand has 10 states, 10 states have (on average 5.0) internal successors, (50), 9 states have internal predecessors, (50), 7 states have call successors, (36), 2 states have call predecessors, (36), 1 states have return successors, (33), 7 states have call predecessors, (33), 7 states have call successors, (33) [2022-04-05 08:26:16,500 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:26:16,500 INFO L93 Difference]: Finished difference Result 1103 states and 1463 transitions. [2022-04-05 08:26:16,501 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-05 08:26:16,501 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 5.0) internal successors, (50), 9 states have internal predecessors, (50), 7 states have call successors, (36), 2 states have call predecessors, (36), 1 states have return successors, (33), 7 states have call predecessors, (33), 7 states have call successors, (33) Word has length 110 [2022-04-05 08:26:16,501 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:26:16,506 INFO L225 Difference]: With dead ends: 1103 [2022-04-05 08:26:16,506 INFO L226 Difference]: Without dead ends: 1097 [2022-04-05 08:26:16,506 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 220 GetRequests, 207 SyntacticMatches, 4 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=24, Invalid=86, Unknown=0, NotChecked=0, Total=110 [2022-04-05 08:26:16,507 INFO L913 BasicCegarLoop]: 65 mSDtfsCounter, 3 mSDsluCounter, 197 mSDsCounter, 0 mSdLazyCounter, 159 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 262 SdHoareTripleChecker+Invalid, 159 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 159 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-04-05 08:26:16,507 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [3 Valid, 262 Invalid, 159 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 159 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-04-05 08:26:16,508 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1097 states. [2022-04-05 08:26:16,632 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1097 to 1097. [2022-04-05 08:26:16,634 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1097 states, 729 states have (on average 1.242798353909465) internal successors, (906), 758 states have internal predecessors, (906), 279 states have call successors, (279), 90 states have call predecessors, (279), 88 states have return successors, (270), 248 states have call predecessors, (270), 270 states have call successors, (270) [2022-04-05 08:26:16,639 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1097 states to 1097 states and 1455 transitions. [2022-04-05 08:26:16,639 INFO L78 Accepts]: Start accepts. Automaton has 1097 states and 1455 transitions. Word has length 110 [2022-04-05 08:26:16,640 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:26:16,640 INFO L478 AbstractCegarLoop]: Abstraction has 1097 states and 1455 transitions. [2022-04-05 08:26:16,640 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 5.0) internal successors, (50), 9 states have internal predecessors, (50), 7 states have call successors, (36), 2 states have call predecessors, (36), 1 states have return successors, (33), 7 states have call predecessors, (33), 7 states have call successors, (33) [2022-04-05 08:26:16,640 INFO L276 IsEmpty]: Start isEmpty. Operand 1097 states and 1455 transitions. [2022-04-05 08:26:16,641 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 125 [2022-04-05 08:26:16,641 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:26:16,641 INFO L499 BasicCegarLoop]: trace histogram [19, 18, 18, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:26:16,669 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2022-04-05 08:26:16,858 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2022-04-05 08:26:16,858 INFO L403 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:26:16,858 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:26:16,859 INFO L85 PathProgramCache]: Analyzing trace with hash 848408867, now seen corresponding path program 2 times [2022-04-05 08:26:16,859 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:26:16,859 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1975324572] [2022-04-05 08:26:16,859 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:26:16,859 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:26:16,870 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 08:26:16,870 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1268638957] [2022-04-05 08:26:16,871 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-05 08:26:16,871 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:26:16,871 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 08:26:16,872 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 08:26:16,903 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2022-04-05 08:26:16,941 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-05 08:26:16,941 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 08:26:16,943 INFO L263 TraceCheckSpWp]: Trace formula consists of 310 conjuncts, 12 conjunts are in the unsatisfiable core [2022-04-05 08:26:16,945 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 08:26:17,119 INFO L134 CoverageAnalysis]: Checked inductivity of 699 backedges. 102 proven. 51 refuted. 0 times theorem prover too weak. 546 trivial. 0 not checked. [2022-04-05 08:26:17,120 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 08:26:17,450 INFO L134 CoverageAnalysis]: Checked inductivity of 699 backedges. 69 proven. 18 refuted. 0 times theorem prover too weak. 612 trivial. 0 not checked. [2022-04-05 08:26:17,451 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:26:17,451 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1975324572] [2022-04-05 08:26:17,451 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 08:26:17,451 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1268638957] [2022-04-05 08:26:17,451 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1268638957] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 08:26:17,451 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 08:26:17,451 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2022-04-05 08:26:17,451 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [655622032] [2022-04-05 08:26:17,451 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 08:26:17,452 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-05 08:26:17,452 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:26:17,452 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-05 08:26:17,452 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2022-04-05 08:26:17,453 INFO L87 Difference]: Start difference. First operand 1097 states and 1455 transitions. Second operand has 9 states, 9 states have (on average 6.222222222222222) internal successors, (56), 9 states have internal predecessors, (56), 9 states have call successors, (37), 2 states have call predecessors, (37), 2 states have return successors, (35), 9 states have call predecessors, (35), 9 states have call successors, (35) [2022-04-05 08:26:17,635 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:26:17,636 INFO L93 Difference]: Finished difference Result 1320 states and 1738 transitions. [2022-04-05 08:26:17,636 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-05 08:26:17,637 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 6.222222222222222) internal successors, (56), 9 states have internal predecessors, (56), 9 states have call successors, (37), 2 states have call predecessors, (37), 2 states have return successors, (35), 9 states have call predecessors, (35), 9 states have call successors, (35) Word has length 124 [2022-04-05 08:26:17,638 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:26:17,641 INFO L225 Difference]: With dead ends: 1320 [2022-04-05 08:26:17,642 INFO L226 Difference]: Without dead ends: 907 [2022-04-05 08:26:17,643 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 247 GetRequests, 237 SyntacticMatches, 3 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2022-04-05 08:26:17,643 INFO L913 BasicCegarLoop]: 67 mSDtfsCounter, 3 mSDsluCounter, 200 mSDsCounter, 0 mSdLazyCounter, 124 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 267 SdHoareTripleChecker+Invalid, 132 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 124 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 08:26:17,644 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [4 Valid, 267 Invalid, 132 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 124 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 08:26:17,644 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 907 states. [2022-04-05 08:26:17,730 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 907 to 905. [2022-04-05 08:26:17,732 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 905 states, 598 states have (on average 1.2040133779264215) internal successors, (720), 627 states have internal predecessors, (720), 221 states have call successors, (221), 87 states have call predecessors, (221), 85 states have return successors, (212), 190 states have call predecessors, (212), 212 states have call successors, (212) [2022-04-05 08:26:17,735 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 905 states to 905 states and 1153 transitions. [2022-04-05 08:26:17,736 INFO L78 Accepts]: Start accepts. Automaton has 905 states and 1153 transitions. Word has length 124 [2022-04-05 08:26:17,736 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:26:17,736 INFO L478 AbstractCegarLoop]: Abstraction has 905 states and 1153 transitions. [2022-04-05 08:26:17,737 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 6.222222222222222) internal successors, (56), 9 states have internal predecessors, (56), 9 states have call successors, (37), 2 states have call predecessors, (37), 2 states have return successors, (35), 9 states have call predecessors, (35), 9 states have call successors, (35) [2022-04-05 08:26:17,737 INFO L276 IsEmpty]: Start isEmpty. Operand 905 states and 1153 transitions. [2022-04-05 08:26:17,739 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 127 [2022-04-05 08:26:17,739 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:26:17,739 INFO L499 BasicCegarLoop]: trace histogram [19, 18, 18, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:26:17,763 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2022-04-05 08:26:17,963 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable17,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:26:17,964 INFO L403 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:26:17,964 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:26:17,964 INFO L85 PathProgramCache]: Analyzing trace with hash 722879610, now seen corresponding path program 3 times [2022-04-05 08:26:17,964 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:26:17,964 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [233175009] [2022-04-05 08:26:17,964 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:26:17,965 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:26:17,973 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 08:26:17,973 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1934712907] [2022-04-05 08:26:17,973 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-04-05 08:26:17,973 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:26:17,973 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 08:26:17,974 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 08:26:17,986 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2022-04-05 08:26:18,051 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2022-04-05 08:26:18,051 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 08:26:18,056 INFO L263 TraceCheckSpWp]: Trace formula consists of 216 conjuncts, 26 conjunts are in the unsatisfiable core [2022-04-05 08:26:18,059 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 08:26:18,465 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-05 08:26:18,486 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-05 08:26:18,514 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-05 08:26:18,640 INFO L134 CoverageAnalysis]: Checked inductivity of 711 backedges. 145 proven. 2 refuted. 0 times theorem prover too weak. 564 trivial. 0 not checked. [2022-04-05 08:26:18,641 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 08:30:34,933 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:30:34,934 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [233175009] [2022-04-05 08:30:34,934 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 08:30:34,934 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1934712907] [2022-04-05 08:30:34,934 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1934712907] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-05 08:30:34,934 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-05 08:30:34,934 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2022-04-05 08:30:34,934 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1984419662] [2022-04-05 08:30:34,934 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-05 08:30:34,934 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-05 08:30:34,934 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:30:34,935 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-05 08:30:34,935 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=49, Invalid=189, Unknown=2, NotChecked=0, Total=240 [2022-04-05 08:30:34,935 INFO L87 Difference]: Start difference. First operand 905 states and 1153 transitions. Second operand has 9 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 8 states have internal predecessors, (24), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 4 states have call predecessors, (8), 3 states have call successors, (8) [2022-04-05 08:30:35,207 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:30:35,207 INFO L93 Difference]: Finished difference Result 935 states and 1182 transitions. [2022-04-05 08:30:35,207 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-05 08:30:35,207 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 8 states have internal predecessors, (24), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 4 states have call predecessors, (8), 3 states have call successors, (8) Word has length 126 [2022-04-05 08:30:35,208 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:30:35,211 INFO L225 Difference]: With dead ends: 935 [2022-04-05 08:30:35,211 INFO L226 Difference]: Without dead ends: 921 [2022-04-05 08:30:35,212 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 150 GetRequests, 131 SyntacticMatches, 3 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 51 ImplicationChecksByTransitivity, 16.5s TimeCoverageRelationStatistics Valid=62, Invalid=242, Unknown=2, NotChecked=0, Total=306 [2022-04-05 08:30:35,212 INFO L913 BasicCegarLoop]: 23 mSDtfsCounter, 29 mSDsluCounter, 62 mSDsCounter, 0 mSdLazyCounter, 105 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 85 SdHoareTripleChecker+Invalid, 120 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 105 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 08:30:35,213 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [34 Valid, 85 Invalid, 120 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 105 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 08:30:35,214 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 921 states. [2022-04-05 08:30:35,286 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 921 to 695. [2022-04-05 08:30:35,287 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 695 states, 468 states have (on average 1.1752136752136753) internal successors, (550), 470 states have internal predecessors, (550), 153 states have call successors, (153), 75 states have call predecessors, (153), 73 states have return successors, (150), 149 states have call predecessors, (150), 150 states have call successors, (150) [2022-04-05 08:30:35,290 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 695 states to 695 states and 853 transitions. [2022-04-05 08:30:35,290 INFO L78 Accepts]: Start accepts. Automaton has 695 states and 853 transitions. Word has length 126 [2022-04-05 08:30:35,290 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:30:35,290 INFO L478 AbstractCegarLoop]: Abstraction has 695 states and 853 transitions. [2022-04-05 08:30:35,290 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 8 states have internal predecessors, (24), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 4 states have call predecessors, (8), 3 states have call successors, (8) [2022-04-05 08:30:35,291 INFO L276 IsEmpty]: Start isEmpty. Operand 695 states and 853 transitions. [2022-04-05 08:30:35,292 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 129 [2022-04-05 08:30:35,292 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:30:35,292 INFO L499 BasicCegarLoop]: trace histogram [20, 19, 19, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:30:35,315 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2022-04-05 08:30:35,511 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:30:35,511 INFO L403 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:30:35,512 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:30:35,512 INFO L85 PathProgramCache]: Analyzing trace with hash -1722143882, now seen corresponding path program 3 times [2022-04-05 08:30:35,512 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:30:35,512 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1666491094] [2022-04-05 08:30:35,512 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:30:35,512 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:30:35,519 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 08:30:35,520 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1094228966] [2022-04-05 08:30:35,520 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-04-05 08:30:35,520 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:30:35,520 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 08:30:35,522 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 08:30:35,539 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2022-04-05 08:30:35,582 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2022-04-05 08:30:35,582 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 08:30:35,583 INFO L263 TraceCheckSpWp]: Trace formula consists of 188 conjuncts, 12 conjunts are in the unsatisfiable core [2022-04-05 08:30:35,585 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 08:30:35,771 INFO L134 CoverageAnalysis]: Checked inductivity of 774 backedges. 90 proven. 4 refuted. 0 times theorem prover too weak. 680 trivial. 0 not checked. [2022-04-05 08:30:35,772 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 08:30:35,984 INFO L134 CoverageAnalysis]: Checked inductivity of 774 backedges. 90 proven. 4 refuted. 0 times theorem prover too weak. 680 trivial. 0 not checked. [2022-04-05 08:30:35,984 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:30:35,984 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1666491094] [2022-04-05 08:30:35,984 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 08:30:35,984 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1094228966] [2022-04-05 08:30:35,984 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1094228966] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 08:30:35,984 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 08:30:35,984 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 12 [2022-04-05 08:30:35,984 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2138068254] [2022-04-05 08:30:35,984 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 08:30:35,985 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-04-05 08:30:35,985 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:30:35,985 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-04-05 08:30:35,985 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=101, Unknown=0, NotChecked=0, Total=132 [2022-04-05 08:30:35,986 INFO L87 Difference]: Start difference. First operand 695 states and 853 transitions. Second operand has 12 states, 10 states have (on average 3.3) internal successors, (33), 9 states have internal predecessors, (33), 4 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 6 states have call predecessors, (15), 4 states have call successors, (15) [2022-04-05 08:30:36,178 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:30:36,178 INFO L93 Difference]: Finished difference Result 771 states and 912 transitions. [2022-04-05 08:30:36,178 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-05 08:30:36,179 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 10 states have (on average 3.3) internal successors, (33), 9 states have internal predecessors, (33), 4 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 6 states have call predecessors, (15), 4 states have call successors, (15) Word has length 128 [2022-04-05 08:30:36,179 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:30:36,182 INFO L225 Difference]: With dead ends: 771 [2022-04-05 08:30:36,182 INFO L226 Difference]: Without dead ends: 755 [2022-04-05 08:30:36,182 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 259 GetRequests, 245 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 27 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=51, Invalid=159, Unknown=0, NotChecked=0, Total=210 [2022-04-05 08:30:36,183 INFO L913 BasicCegarLoop]: 23 mSDtfsCounter, 39 mSDsluCounter, 94 mSDsCounter, 0 mSdLazyCounter, 152 mSolverCounterSat, 32 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 117 SdHoareTripleChecker+Invalid, 184 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 32 IncrementalHoareTripleChecker+Valid, 152 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 08:30:36,183 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [44 Valid, 117 Invalid, 184 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [32 Valid, 152 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 08:30:36,187 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 755 states. [2022-04-05 08:30:36,248 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 755 to 539. [2022-04-05 08:30:36,249 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 539 states, 362 states have (on average 1.1049723756906078) internal successors, (400), 373 states have internal predecessors, (400), 103 states have call successors, (103), 74 states have call predecessors, (103), 73 states have return successors, (101), 91 states have call predecessors, (101), 101 states have call successors, (101) [2022-04-05 08:30:36,251 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 539 states to 539 states and 604 transitions. [2022-04-05 08:30:36,251 INFO L78 Accepts]: Start accepts. Automaton has 539 states and 604 transitions. Word has length 128 [2022-04-05 08:30:36,252 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:30:36,252 INFO L478 AbstractCegarLoop]: Abstraction has 539 states and 604 transitions. [2022-04-05 08:30:36,252 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 10 states have (on average 3.3) internal successors, (33), 9 states have internal predecessors, (33), 4 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 6 states have call predecessors, (15), 4 states have call successors, (15) [2022-04-05 08:30:36,252 INFO L276 IsEmpty]: Start isEmpty. Operand 539 states and 604 transitions. [2022-04-05 08:30:36,254 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 225 [2022-04-05 08:30:36,254 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:30:36,255 INFO L499 BasicCegarLoop]: trace histogram [33, 32, 32, 11, 10, 10, 10, 10, 10, 10, 10, 4, 4, 4, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:30:36,278 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2022-04-05 08:30:36,477 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:30:36,478 INFO L403 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:30:36,478 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:30:36,478 INFO L85 PathProgramCache]: Analyzing trace with hash -206704767, now seen corresponding path program 2 times [2022-04-05 08:30:36,479 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:30:36,479 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1171520804] [2022-04-05 08:30:36,479 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:30:36,479 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:30:36,492 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 08:30:36,492 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [661356339] [2022-04-05 08:30:36,492 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-05 08:30:36,492 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:30:36,493 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 08:30:36,494 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 08:30:36,522 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2022-04-05 08:30:36,596 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-05 08:30:36,596 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 08:30:36,598 INFO L263 TraceCheckSpWp]: Trace formula consists of 549 conjuncts, 33 conjunts are in the unsatisfiable core [2022-04-05 08:30:36,605 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 08:30:37,026 INFO L134 CoverageAnalysis]: Checked inductivity of 2374 backedges. 64 proven. 2222 refuted. 0 times theorem prover too weak. 88 trivial. 0 not checked. [2022-04-05 08:30:37,026 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 08:30:37,575 INFO L134 CoverageAnalysis]: Checked inductivity of 2374 backedges. 64 proven. 326 refuted. 0 times theorem prover too weak. 1984 trivial. 0 not checked. [2022-04-05 08:30:37,575 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:30:37,575 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1171520804] [2022-04-05 08:30:37,575 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 08:30:37,576 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [661356339] [2022-04-05 08:30:37,576 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [661356339] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 08:30:37,576 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 08:30:37,576 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 34 [2022-04-05 08:30:37,576 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [140599777] [2022-04-05 08:30:37,576 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 08:30:37,576 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 34 states [2022-04-05 08:30:37,576 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:30:37,577 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2022-04-05 08:30:37,577 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=501, Invalid=621, Unknown=0, NotChecked=0, Total=1122 [2022-04-05 08:30:37,578 INFO L87 Difference]: Start difference. First operand 539 states and 604 transitions. Second operand has 34 states, 34 states have (on average 4.764705882352941) internal successors, (162), 34 states have internal predecessors, (162), 32 states have call successors, (68), 18 states have call predecessors, (68), 17 states have return successors, (66), 30 states have call predecessors, (66), 29 states have call successors, (66) [2022-04-05 08:30:38,857 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:30:38,858 INFO L93 Difference]: Finished difference Result 1289 states and 1514 transitions. [2022-04-05 08:30:38,858 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 58 states. [2022-04-05 08:30:38,859 INFO L78 Accepts]: Start accepts. Automaton has has 34 states, 34 states have (on average 4.764705882352941) internal successors, (162), 34 states have internal predecessors, (162), 32 states have call successors, (68), 18 states have call predecessors, (68), 17 states have return successors, (66), 30 states have call predecessors, (66), 29 states have call successors, (66) Word has length 224 [2022-04-05 08:30:38,859 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:30:38,863 INFO L225 Difference]: With dead ends: 1289 [2022-04-05 08:30:38,864 INFO L226 Difference]: Without dead ends: 1276 [2022-04-05 08:30:38,865 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 472 GetRequests, 415 SyntacticMatches, 0 SemanticMatches, 57 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 434 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=1212, Invalid=2210, Unknown=0, NotChecked=0, Total=3422 [2022-04-05 08:30:38,865 INFO L913 BasicCegarLoop]: 169 mSDtfsCounter, 841 mSDsluCounter, 499 mSDsCounter, 0 mSdLazyCounter, 602 mSolverCounterSat, 770 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 841 SdHoareTripleChecker+Valid, 668 SdHoareTripleChecker+Invalid, 1372 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 770 IncrementalHoareTripleChecker+Valid, 602 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2022-04-05 08:30:38,866 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [841 Valid, 668 Invalid, 1372 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [770 Valid, 602 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2022-04-05 08:30:38,867 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1276 states. [2022-04-05 08:30:39,017 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1276 to 1275. [2022-04-05 08:30:39,019 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1275 states, 858 states have (on average 1.118881118881119) internal successors, (960), 885 states have internal predecessors, (960), 247 states have call successors, (247), 170 states have call predecessors, (247), 169 states have return successors, (245), 219 states have call predecessors, (245), 245 states have call successors, (245) [2022-04-05 08:30:39,022 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1275 states to 1275 states and 1452 transitions. [2022-04-05 08:30:39,022 INFO L78 Accepts]: Start accepts. Automaton has 1275 states and 1452 transitions. Word has length 224 [2022-04-05 08:30:39,023 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:30:39,023 INFO L478 AbstractCegarLoop]: Abstraction has 1275 states and 1452 transitions. [2022-04-05 08:30:39,023 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 34 states, 34 states have (on average 4.764705882352941) internal successors, (162), 34 states have internal predecessors, (162), 32 states have call successors, (68), 18 states have call predecessors, (68), 17 states have return successors, (66), 30 states have call predecessors, (66), 29 states have call successors, (66) [2022-04-05 08:30:39,023 INFO L276 IsEmpty]: Start isEmpty. Operand 1275 states and 1452 transitions. [2022-04-05 08:30:39,030 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 449 [2022-04-05 08:30:39,030 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:30:39,031 INFO L499 BasicCegarLoop]: trace histogram [65, 64, 64, 27, 26, 26, 26, 26, 26, 26, 26, 4, 4, 4, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:30:39,057 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2022-04-05 08:30:39,254 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20,18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:30:39,254 INFO L403 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:30:39,254 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:30:39,254 INFO L85 PathProgramCache]: Analyzing trace with hash 1366842977, now seen corresponding path program 3 times [2022-04-05 08:30:39,254 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:30:39,255 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2010349210] [2022-04-05 08:30:39,255 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:30:39,255 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:30:39,271 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 08:30:39,272 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [632670722] [2022-04-05 08:30:39,272 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-04-05 08:30:39,272 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:30:39,272 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 08:30:39,273 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 08:30:39,275 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2022-04-05 08:30:42,076 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 42 check-sat command(s) [2022-04-05 08:30:42,076 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 08:30:42,086 INFO L263 TraceCheckSpWp]: Trace formula consists of 1068 conjuncts, 65 conjunts are in the unsatisfiable core [2022-04-05 08:30:42,092 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 08:30:43,080 INFO L134 CoverageAnalysis]: Checked inductivity of 10230 backedges. 128 proven. 9950 refuted. 0 times theorem prover too weak. 152 trivial. 0 not checked. [2022-04-05 08:30:43,081 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 08:30:44,290 INFO L134 CoverageAnalysis]: Checked inductivity of 10230 backedges. 128 proven. 2038 refuted. 0 times theorem prover too weak. 8064 trivial. 0 not checked. [2022-04-05 08:30:44,290 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:30:44,290 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2010349210] [2022-04-05 08:30:44,291 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 08:30:44,291 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [632670722] [2022-04-05 08:30:44,291 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [632670722] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 08:30:44,291 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 08:30:44,291 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [34, 34] total 54 [2022-04-05 08:30:44,291 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [384735738] [2022-04-05 08:30:44,291 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 08:30:44,293 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 54 states [2022-04-05 08:30:44,294 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:30:44,294 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 54 interpolants. [2022-04-05 08:30:44,295 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1331, Invalid=1531, Unknown=0, NotChecked=0, Total=2862 [2022-04-05 08:30:44,295 INFO L87 Difference]: Start difference. First operand 1275 states and 1452 transitions. Second operand has 54 states, 54 states have (on average 5.7407407407407405) internal successors, (310), 54 states have internal predecessors, (310), 52 states have call successors, (132), 33 states have call predecessors, (132), 32 states have return successors, (130), 50 states have call predecessors, (130), 50 states have call successors, (130) [2022-04-05 08:30:46,705 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:30:46,705 INFO L93 Difference]: Finished difference Result 2209 states and 2586 transitions. [2022-04-05 08:30:46,707 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 98 states. [2022-04-05 08:30:46,708 INFO L78 Accepts]: Start accepts. Automaton has has 54 states, 54 states have (on average 5.7407407407407405) internal successors, (310), 54 states have internal predecessors, (310), 52 states have call successors, (132), 33 states have call predecessors, (132), 32 states have return successors, (130), 50 states have call predecessors, (130), 50 states have call successors, (130) Word has length 448 [2022-04-05 08:30:46,708 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:30:46,715 INFO L225 Difference]: With dead ends: 2209 [2022-04-05 08:30:46,716 INFO L226 Difference]: Without dead ends: 2196 [2022-04-05 08:30:46,718 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 940 GetRequests, 842 SyntacticMatches, 1 SemanticMatches, 97 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1241 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=3518, Invalid=6184, Unknown=0, NotChecked=0, Total=9702 [2022-04-05 08:30:46,718 INFO L913 BasicCegarLoop]: 269 mSDtfsCounter, 1489 mSDsluCounter, 805 mSDsCounter, 0 mSdLazyCounter, 1240 mSolverCounterSat, 1140 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1489 SdHoareTripleChecker+Valid, 1074 SdHoareTripleChecker+Invalid, 2380 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1140 IncrementalHoareTripleChecker+Valid, 1240 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.1s IncrementalHoareTripleChecker+Time [2022-04-05 08:30:46,719 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [1489 Valid, 1074 Invalid, 2380 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1140 Valid, 1240 Invalid, 0 Unknown, 0 Unchecked, 1.1s Time] [2022-04-05 08:30:46,720 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2196 states. [2022-04-05 08:30:46,979 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2196 to 2195. [2022-04-05 08:30:46,981 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2195 states, 1478 states have (on average 1.1231393775372125) internal successors, (1660), 1525 states have internal predecessors, (1660), 427 states have call successors, (427), 290 states have call predecessors, (427), 289 states have return successors, (425), 379 states have call predecessors, (425), 425 states have call successors, (425) [2022-04-05 08:30:46,987 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2195 states to 2195 states and 2512 transitions. [2022-04-05 08:30:46,987 INFO L78 Accepts]: Start accepts. Automaton has 2195 states and 2512 transitions. Word has length 448 [2022-04-05 08:30:46,988 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:30:46,988 INFO L478 AbstractCegarLoop]: Abstraction has 2195 states and 2512 transitions. [2022-04-05 08:30:46,988 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 54 states, 54 states have (on average 5.7407407407407405) internal successors, (310), 54 states have internal predecessors, (310), 52 states have call successors, (132), 33 states have call predecessors, (132), 32 states have return successors, (130), 50 states have call predecessors, (130), 50 states have call successors, (130) [2022-04-05 08:30:46,989 INFO L276 IsEmpty]: Start isEmpty. Operand 2195 states and 2512 transitions. [2022-04-05 08:30:47,004 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 729 [2022-04-05 08:30:47,005 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:30:47,005 INFO L499 BasicCegarLoop]: trace histogram [105, 104, 104, 47, 46, 46, 46, 46, 46, 46, 46, 4, 4, 4, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:30:47,017 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2022-04-05 08:30:47,217 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable21,19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:30:47,218 INFO L403 AbstractCegarLoop]: === Iteration 23 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:30:47,219 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:30:47,219 INFO L85 PathProgramCache]: Analyzing trace with hash -694651655, now seen corresponding path program 4 times [2022-04-05 08:30:47,219 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:30:47,219 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1853120647] [2022-04-05 08:30:47,219 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:30:47,219 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:30:47,241 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 08:30:47,241 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [495849764] [2022-04-05 08:30:47,241 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-05 08:30:47,241 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:30:47,242 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 08:30:47,242 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 08:30:47,297 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process