/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerCTransformed.xml -s ../../../trunk/examples/settings/loopacceleration/qvasr/qvasr_64.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/dijkstra-u_unwindbound10.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-7390193 [2022-04-05 06:52:04,918 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-05 06:52:04,919 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-05 06:52:04,949 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-05 06:52:04,949 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-05 06:52:04,950 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-05 06:52:04,951 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-05 06:52:04,952 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-05 06:52:04,953 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-05 06:52:04,954 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-05 06:52:04,954 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-05 06:52:04,955 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-05 06:52:04,955 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-05 06:52:04,956 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-05 06:52:04,957 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-05 06:52:04,957 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-05 06:52:04,958 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-05 06:52:04,958 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-05 06:52:04,960 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-05 06:52:04,961 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-05 06:52:04,962 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-05 06:52:04,963 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-05 06:52:04,963 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-05 06:52:04,964 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-05 06:52:04,964 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-05 06:52:04,966 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-05 06:52:04,966 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-05 06:52:04,967 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-05 06:52:04,967 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-05 06:52:04,968 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-05 06:52:04,968 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-05 06:52:04,968 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-05 06:52:04,969 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-05 06:52:04,969 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-05 06:52:04,970 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-05 06:52:04,970 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-05 06:52:04,971 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-05 06:52:04,971 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-05 06:52:04,971 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-05 06:52:04,971 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-05 06:52:04,972 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-05 06:52:04,972 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-05 06:52:04,973 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 06:52:05,008 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-05 06:52:05,008 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-05 06:52:05,009 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-04-05 06:52:05,009 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-04-05 06:52:05,009 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-04-05 06:52:05,010 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-04-05 06:52:05,010 INFO L138 SettingsManager]: * Use SBE=true [2022-04-05 06:52:05,010 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-05 06:52:05,010 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-05 06:52:05,010 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-05 06:52:05,010 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-05 06:52:05,010 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-05 06:52:05,010 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-05 06:52:05,011 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-05 06:52:05,011 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-05 06:52:05,011 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-05 06:52:05,011 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-05 06:52:05,011 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-05 06:52:05,011 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-05 06:52:05,011 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-05 06:52:05,011 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-05 06:52:05,012 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-04-05 06:52:05,012 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-04-05 06:52:05,012 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-04-05 06:52:05,012 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-04-05 06:52:05,012 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-05 06:52:05,012 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2022-04-05 06:52:05,012 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2022-04-05 06:52:05,013 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-04-05 06:52:05,013 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 06:52:05,210 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-05 06:52:05,227 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-05 06:52:05,229 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-05 06:52:05,229 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-05 06:52:05,230 INFO L275 PluginConnector]: CDTParser initialized [2022-04-05 06:52:05,231 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/dijkstra-u_unwindbound10.c [2022-04-05 06:52:05,270 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/e593db112/89a6d4d7ba7340aab2995fea7bc53e02/FLAGc1a838c12 [2022-04-05 06:52:05,638 INFO L306 CDTParser]: Found 1 translation units. [2022-04-05 06:52:05,638 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/dijkstra-u_unwindbound10.c [2022-04-05 06:52:05,651 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/e593db112/89a6d4d7ba7340aab2995fea7bc53e02/FLAGc1a838c12 [2022-04-05 06:52:05,658 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/e593db112/89a6d4d7ba7340aab2995fea7bc53e02 [2022-04-05 06:52:05,660 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-05 06:52:05,662 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-04-05 06:52:05,663 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-05 06:52:05,663 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-05 06:52:05,666 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-05 06:52:05,666 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 05.04 06:52:05" (1/1) ... [2022-04-05 06:52:05,667 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@68c39676 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 06:52:05, skipping insertion in model container [2022-04-05 06:52:05,667 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 05.04 06:52:05" (1/1) ... [2022-04-05 06:52:05,672 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-05 06:52:05,688 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-05 06:52:05,801 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/dijkstra-u_unwindbound10.c[525,538] [2022-04-05 06:52:05,823 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-05 06:52:05,831 INFO L203 MainTranslator]: Completed pre-run [2022-04-05 06:52:05,837 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/dijkstra-u_unwindbound10.c[525,538] [2022-04-05 06:52:05,846 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-05 06:52:05,853 INFO L208 MainTranslator]: Completed translation [2022-04-05 06:52:05,853 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 06:52:05 WrapperNode [2022-04-05 06:52:05,853 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-05 06:52:05,854 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-05 06:52:05,854 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-05 06:52:05,854 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-05 06:52:05,861 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 06:52:05" (1/1) ... [2022-04-05 06:52:05,861 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 06:52:05" (1/1) ... [2022-04-05 06:52:05,866 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 06:52:05" (1/1) ... [2022-04-05 06:52:05,866 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 06:52:05" (1/1) ... [2022-04-05 06:52:05,869 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 06:52:05" (1/1) ... [2022-04-05 06:52:05,871 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 06:52:05" (1/1) ... [2022-04-05 06:52:05,872 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 06:52:05" (1/1) ... [2022-04-05 06:52:05,873 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-05 06:52:05,874 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-05 06:52:05,874 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-05 06:52:05,874 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-05 06:52:05,874 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 06:52:05" (1/1) ... [2022-04-05 06:52:05,892 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-05 06:52:05,899 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 06:52:05,908 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 06:52:05,909 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 06:52:05,931 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-05 06:52:05,932 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-05 06:52:05,933 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-05 06:52:05,933 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-05 06:52:05,933 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-05 06:52:05,933 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-05 06:52:05,933 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-05 06:52:05,934 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-05 06:52:05,935 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-05 06:52:05,935 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-05 06:52:05,936 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_uint [2022-04-05 06:52:05,936 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-05 06:52:05,936 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-05 06:52:05,936 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-05 06:52:05,936 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-05 06:52:05,936 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-05 06:52:05,936 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-05 06:52:05,939 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-05 06:52:05,939 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-05 06:52:05,939 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-05 06:52:05,979 INFO L234 CfgBuilder]: Building ICFG [2022-04-05 06:52:05,980 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-05 06:52:06,180 INFO L275 CfgBuilder]: Performing block encoding [2022-04-05 06:52:06,184 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-05 06:52:06,185 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-04-05 06:52:06,186 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 05.04 06:52:06 BoogieIcfgContainer [2022-04-05 06:52:06,186 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-05 06:52:06,186 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-04-05 06:52:06,186 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-04-05 06:52:06,192 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-04-05 06:52:06,194 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 05.04 06:52:06" (1/1) ... [2022-04-05 06:52:06,195 INFO L168 ansformationObserver]: Applying ICFG transformation LOOP_ACCELERATION_QVASR [2022-04-05 06:52:06,224 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 05.04 06:52:06 BasicIcfg [2022-04-05 06:52:06,225 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-04-05 06:52:06,228 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-05 06:52:06,228 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-05 06:52:06,230 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-05 06:52:06,230 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 05.04 06:52:05" (1/4) ... [2022-04-05 06:52:06,231 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@721ae8cf and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 05.04 06:52:06, skipping insertion in model container [2022-04-05 06:52:06,231 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 06:52:05" (2/4) ... [2022-04-05 06:52:06,231 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@721ae8cf and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 05.04 06:52:06, skipping insertion in model container [2022-04-05 06:52:06,231 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 05.04 06:52:06" (3/4) ... [2022-04-05 06:52:06,232 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@721ae8cf and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 05.04 06:52:06, skipping insertion in model container [2022-04-05 06:52:06,232 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 05.04 06:52:06" (4/4) ... [2022-04-05 06:52:06,232 INFO L111 eAbstractionObserver]: Analyzing ICFG dijkstra-u_unwindbound10.cqvasr [2022-04-05 06:52:06,236 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-04-05 06:52:06,236 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-05 06:52:06,284 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-05 06:52:06,290 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 06:52:06,290 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-05 06:52:06,309 INFO L276 IsEmpty]: Start isEmpty. Operand has 39 states, 21 states have (on average 1.4761904761904763) internal successors, (31), 22 states have internal predecessors, (31), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-05 06:52:06,312 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-04-05 06:52:06,312 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 06:52:06,313 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 06:52:06,313 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 06:52:06,316 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 06:52:06,317 INFO L85 PathProgramCache]: Analyzing trace with hash -460462115, now seen corresponding path program 1 times [2022-04-05 06:52:06,322 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 06:52:06,323 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [933330121] [2022-04-05 06:52:06,323 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:52:06,324 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 06:52:06,404 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:52:06,462 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-05 06:52:06,468 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:52:06,483 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-05 06:52:06,484 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:52:06,490 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 06:52:06,491 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 06:52:06,491 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [933330121] [2022-04-05 06:52:06,491 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [933330121] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 06:52:06,492 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 06:52:06,492 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-05 06:52:06,493 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [216376981] [2022-04-05 06:52:06,493 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 06:52:06,497 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-05 06:52:06,497 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 06:52:06,517 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-05 06:52:06,519 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-05 06:52:06,520 INFO L87 Difference]: Start difference. First operand has 39 states, 21 states have (on average 1.4761904761904763) internal successors, (31), 22 states have internal predecessors, (31), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-05 06:52:08,662 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-05 06:52:08,724 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 06:52:08,724 INFO L93 Difference]: Finished difference Result 70 states and 111 transitions. [2022-04-05 06:52:08,725 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-05 06:52:08,726 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2022-04-05 06:52:08,727 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 06:52:08,731 INFO L225 Difference]: With dead ends: 70 [2022-04-05 06:52:08,731 INFO L226 Difference]: Without dead ends: 35 [2022-04-05 06:52:08,733 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-05 06:52:08,736 INFO L913 BasicCegarLoop]: 49 mSDtfsCounter, 10 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 11 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 53 SdHoareTripleChecker+Invalid, 37 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.2s IncrementalHoareTripleChecker+Time [2022-04-05 06:52:08,737 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 53 Invalid, 37 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 25 Invalid, 1 Unknown, 0 Unchecked, 2.2s Time] [2022-04-05 06:52:08,750 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2022-04-05 06:52:08,777 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 34. [2022-04-05 06:52:08,778 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-05 06:52:08,783 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 46 transitions. [2022-04-05 06:52:08,784 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 46 transitions. Word has length 18 [2022-04-05 06:52:08,784 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 06:52:08,784 INFO L478 AbstractCegarLoop]: Abstraction has 34 states and 46 transitions. [2022-04-05 06:52:08,785 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-05 06:52:08,785 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 46 transitions. [2022-04-05 06:52:08,786 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2022-04-05 06:52:08,786 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 06:52:08,787 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 06:52:08,787 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-05 06:52:08,788 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 06:52:08,789 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 06:52:08,789 INFO L85 PathProgramCache]: Analyzing trace with hash -889932734, now seen corresponding path program 1 times [2022-04-05 06:52:08,789 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 06:52:08,790 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1079743439] [2022-04-05 06:52:08,790 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:52:08,790 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 06:52:08,824 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 06:52:08,824 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1996037127] [2022-04-05 06:52:08,824 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:52:08,825 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 06:52:08,825 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 06:52:08,826 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 06:52:08,850 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 06:52:08,915 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:52:08,917 INFO L263 TraceCheckSpWp]: Trace formula consists of 85 conjuncts, 5 conjunts are in the unsatisfiable core [2022-04-05 06:52:08,920 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 06:52:09,015 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 06:52:09,016 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-05 06:52:09,016 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 06:52:09,016 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1079743439] [2022-04-05 06:52:09,016 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 06:52:09,016 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1996037127] [2022-04-05 06:52:09,017 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1996037127] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 06:52:09,017 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 06:52:09,017 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-05 06:52:09,018 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [355801326] [2022-04-05 06:52:09,018 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 06:52:09,018 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-04-05 06:52:09,018 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 06:52:09,019 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-04-05 06:52:09,019 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-04-05 06:52:09,019 INFO L87 Difference]: Start difference. First operand 34 states and 46 transitions. Second operand has 4 states, 4 states have (on average 3.5) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-05 06:52:09,036 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 06:52:09,036 INFO L93 Difference]: Finished difference Result 55 states and 78 transitions. [2022-04-05 06:52:09,039 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-04-05 06:52:09,039 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 3.5) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 20 [2022-04-05 06:52:09,039 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 06:52:09,040 INFO L225 Difference]: With dead ends: 55 [2022-04-05 06:52:09,040 INFO L226 Difference]: Without dead ends: 36 [2022-04-05 06:52:09,040 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-04-05 06:52:09,041 INFO L913 BasicCegarLoop]: 44 mSDtfsCounter, 0 mSDsluCounter, 75 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 119 SdHoareTripleChecker+Invalid, 8 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 8 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-05 06:52:09,042 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 119 Invalid, 8 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 8 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-05 06:52:09,042 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2022-04-05 06:52:09,047 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 36. [2022-04-05 06:52:09,047 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 20 states have (on average 1.3) internal successors, (26), 21 states have internal predecessors, (26), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-05 06:52:09,048 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 48 transitions. [2022-04-05 06:52:09,049 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 48 transitions. Word has length 20 [2022-04-05 06:52:09,049 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 06:52:09,051 INFO L478 AbstractCegarLoop]: Abstraction has 36 states and 48 transitions. [2022-04-05 06:52:09,051 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 3.5) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-05 06:52:09,051 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 48 transitions. [2022-04-05 06:52:09,051 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2022-04-05 06:52:09,052 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 06:52:09,052 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 06:52:09,079 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 06:52:09,270 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 06:52:09,270 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 06:52:09,271 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 06:52:09,271 INFO L85 PathProgramCache]: Analyzing trace with hash 1699853977, now seen corresponding path program 1 times [2022-04-05 06:52:09,271 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 06:52:09,271 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [528263047] [2022-04-05 06:52:09,271 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:52:09,271 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 06:52:09,282 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 06:52:09,283 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [577243024] [2022-04-05 06:52:09,283 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:52:09,283 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 06:52:09,283 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 06:52:09,284 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 06:52:09,287 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 06:52:09,336 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:52:09,336 INFO L263 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-05 06:52:09,341 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 06:52:09,450 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 06:52:09,450 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-05 06:52:09,451 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 06:52:09,451 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [528263047] [2022-04-05 06:52:09,451 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 06:52:09,451 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [577243024] [2022-04-05 06:52:09,451 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [577243024] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 06:52:09,451 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 06:52:09,451 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-05 06:52:09,452 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [661104214] [2022-04-05 06:52:09,452 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 06:52:09,452 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-05 06:52:09,452 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 06:52:09,453 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-05 06:52:09,453 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-04-05 06:52:09,453 INFO L87 Difference]: Start difference. First operand 36 states and 48 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-05 06:52:09,475 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 06:52:09,475 INFO L93 Difference]: Finished difference Result 49 states and 64 transitions. [2022-04-05 06:52:09,475 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-05 06:52:09,476 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 21 [2022-04-05 06:52:09,476 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 06:52:09,476 INFO L225 Difference]: With dead ends: 49 [2022-04-05 06:52:09,477 INFO L226 Difference]: Without dead ends: 40 [2022-04-05 06:52:09,477 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 20 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-04-05 06:52:09,478 INFO L913 BasicCegarLoop]: 43 mSDtfsCounter, 7 mSDsluCounter, 106 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 149 SdHoareTripleChecker+Invalid, 18 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-05 06:52:09,478 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [7 Valid, 149 Invalid, 18 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-05 06:52:09,479 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2022-04-05 06:52:09,484 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 39. [2022-04-05 06:52:09,484 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 23 states have (on average 1.3043478260869565) internal successors, (30), 24 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-05 06:52:09,485 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 52 transitions. [2022-04-05 06:52:09,485 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 52 transitions. Word has length 21 [2022-04-05 06:52:09,485 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 06:52:09,485 INFO L478 AbstractCegarLoop]: Abstraction has 39 states and 52 transitions. [2022-04-05 06:52:09,486 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-05 06:52:09,486 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 52 transitions. [2022-04-05 06:52:09,486 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2022-04-05 06:52:09,486 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 06:52:09,486 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 06:52:09,512 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2022-04-05 06:52:09,699 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2022-04-05 06:52:09,700 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 06:52:09,700 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 06:52:09,700 INFO L85 PathProgramCache]: Analyzing trace with hash 1700986035, now seen corresponding path program 1 times [2022-04-05 06:52:09,701 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 06:52:09,701 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [854342292] [2022-04-05 06:52:09,701 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:52:09,701 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 06:52:09,738 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:52:09,880 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-05 06:52:09,882 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:52:09,908 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-05 06:52:09,910 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:52:09,914 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 06:52:09,915 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 06:52:09,915 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [854342292] [2022-04-05 06:52:09,915 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [854342292] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 06:52:09,915 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 06:52:09,916 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-04-05 06:52:09,916 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2118416216] [2022-04-05 06:52:09,916 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 06:52:09,916 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-04-05 06:52:09,916 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 06:52:09,917 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-04-05 06:52:09,917 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2022-04-05 06:52:09,917 INFO L87 Difference]: Start difference. First operand 39 states and 52 transitions. Second operand has 7 states, 7 states have (on average 2.142857142857143) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-05 06:52:12,634 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-05 06:52:14,940 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-05 06:52:16,680 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.50s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-05 06:52:20,137 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-05 06:52:22,206 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-05 06:52:22,255 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 06:52:22,256 INFO L93 Difference]: Finished difference Result 72 states and 104 transitions. [2022-04-05 06:52:22,256 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-05 06:52:22,256 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.142857142857143) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 21 [2022-04-05 06:52:22,256 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 06:52:22,258 INFO L225 Difference]: With dead ends: 72 [2022-04-05 06:52:22,258 INFO L226 Difference]: Without dead ends: 51 [2022-04-05 06:52:22,258 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2022-04-05 06:52:22,259 INFO L913 BasicCegarLoop]: 45 mSDtfsCounter, 24 mSDsluCounter, 53 mSDsCounter, 0 mSdLazyCounter, 198 mSolverCounterSat, 40 mSolverCounterUnsat, 4 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 12.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 98 SdHoareTripleChecker+Invalid, 242 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 40 IncrementalHoareTripleChecker+Valid, 198 IncrementalHoareTripleChecker+Invalid, 4 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 12.3s IncrementalHoareTripleChecker+Time [2022-04-05 06:52:22,259 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [25 Valid, 98 Invalid, 242 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [40 Valid, 198 Invalid, 4 Unknown, 0 Unchecked, 12.3s Time] [2022-04-05 06:52:22,260 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2022-04-05 06:52:22,268 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2022-04-05 06:52:22,268 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 29 states have internal predecessors, (34), 19 states have call successors, (19), 5 states have call predecessors, (19), 4 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-05 06:52:22,269 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 69 transitions. [2022-04-05 06:52:22,269 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 69 transitions. Word has length 21 [2022-04-05 06:52:22,269 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 06:52:22,270 INFO L478 AbstractCegarLoop]: Abstraction has 51 states and 69 transitions. [2022-04-05 06:52:22,270 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.142857142857143) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-05 06:52:22,270 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 69 transitions. [2022-04-05 06:52:22,270 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2022-04-05 06:52:22,270 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 06:52:22,271 INFO L499 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 06:52:22,271 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2022-04-05 06:52:22,271 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 06:52:22,271 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 06:52:22,271 INFO L85 PathProgramCache]: Analyzing trace with hash 1908885951, now seen corresponding path program 1 times [2022-04-05 06:52:22,271 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 06:52:22,271 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1001378720] [2022-04-05 06:52:22,272 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:52:22,272 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 06:52:22,279 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 06:52:22,279 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [149386473] [2022-04-05 06:52:22,279 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:52:22,279 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 06:52:22,280 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 06:52:22,291 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 06:52:22,331 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 06:52:22,339 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:52:22,340 INFO L263 TraceCheckSpWp]: Trace formula consists of 93 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-05 06:52:22,345 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 06:52:22,391 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 06:52:22,391 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 06:52:22,447 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 06:52:22,447 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 06:52:22,447 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1001378720] [2022-04-05 06:52:22,447 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 06:52:22,448 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [149386473] [2022-04-05 06:52:22,448 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [149386473] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 06:52:22,448 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 06:52:22,448 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2022-04-05 06:52:22,448 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1874474468] [2022-04-05 06:52:22,448 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 06:52:22,448 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-04-05 06:52:22,449 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 06:52:22,449 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-04-05 06:52:22,449 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2022-04-05 06:52:22,449 INFO L87 Difference]: Start difference. First operand 51 states and 69 transitions. Second operand has 8 states, 8 states have (on average 3.625) internal successors, (29), 8 states have internal predecessors, (29), 4 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2022-04-05 06:52:24,570 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 06:52:26,574 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 06:52:29,927 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 06:52:31,263 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 06:52:31,263 INFO L93 Difference]: Finished difference Result 104 states and 146 transitions. [2022-04-05 06:52:31,264 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-04-05 06:52:31,264 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.625) internal successors, (29), 8 states have internal predecessors, (29), 4 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) Word has length 23 [2022-04-05 06:52:31,264 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 06:52:31,265 INFO L225 Difference]: With dead ends: 104 [2022-04-05 06:52:31,266 INFO L226 Difference]: Without dead ends: 85 [2022-04-05 06:52:31,267 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 48 GetRequests, 39 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=40, Invalid=70, Unknown=0, NotChecked=0, Total=110 [2022-04-05 06:52:31,268 INFO L913 BasicCegarLoop]: 61 mSDtfsCounter, 59 mSDsluCounter, 225 mSDsCounter, 0 mSdLazyCounter, 87 mSolverCounterSat, 11 mSolverCounterUnsat, 3 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 8.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 59 SdHoareTripleChecker+Valid, 286 SdHoareTripleChecker+Invalid, 101 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 87 IncrementalHoareTripleChecker+Invalid, 3 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 8.8s IncrementalHoareTripleChecker+Time [2022-04-05 06:52:31,268 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [59 Valid, 286 Invalid, 101 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 87 Invalid, 3 Unknown, 0 Unchecked, 8.8s Time] [2022-04-05 06:52:31,269 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 85 states. [2022-04-05 06:52:31,280 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 85 to 63. [2022-04-05 06:52:31,280 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 38 states have (on average 1.263157894736842) internal successors, (48), 40 states have internal predecessors, (48), 19 states have call successors, (19), 6 states have call predecessors, (19), 5 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-05 06:52:31,281 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 83 transitions. [2022-04-05 06:52:31,282 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 83 transitions. Word has length 23 [2022-04-05 06:52:31,282 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 06:52:31,282 INFO L478 AbstractCegarLoop]: Abstraction has 63 states and 83 transitions. [2022-04-05 06:52:31,282 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.625) internal successors, (29), 8 states have internal predecessors, (29), 4 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2022-04-05 06:52:31,282 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 83 transitions. [2022-04-05 06:52:31,283 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2022-04-05 06:52:31,283 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 06:52:31,283 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 06:52:31,323 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 06:52:31,507 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 06:52:31,508 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 06:52:31,508 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 06:52:31,508 INFO L85 PathProgramCache]: Analyzing trace with hash -1731080004, now seen corresponding path program 1 times [2022-04-05 06:52:31,508 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 06:52:31,508 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1041179770] [2022-04-05 06:52:31,508 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:52:31,509 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 06:52:31,529 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 06:52:31,529 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1946096760] [2022-04-05 06:52:31,529 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:52:31,529 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 06:52:31,530 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 06:52:31,538 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 06:52:31,540 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 06:52:31,575 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:52:31,576 INFO L263 TraceCheckSpWp]: Trace formula consists of 94 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-05 06:52:31,578 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 06:52:31,638 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 06:52:31,638 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 06:52:31,709 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 06:52:31,710 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 06:52:31,710 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1041179770] [2022-04-05 06:52:31,710 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 06:52:31,710 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1946096760] [2022-04-05 06:52:31,710 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1946096760] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 06:52:31,710 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 06:52:31,710 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2022-04-05 06:52:31,711 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [951641435] [2022-04-05 06:52:31,711 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 06:52:31,711 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-04-05 06:52:31,711 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 06:52:31,711 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-04-05 06:52:31,712 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2022-04-05 06:52:31,712 INFO L87 Difference]: Start difference. First operand 63 states and 83 transitions. Second operand has 10 states, 10 states have (on average 3.3) internal successors, (33), 10 states have internal predecessors, (33), 4 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2022-04-05 06:52:35,221 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 06:52:38,837 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 06:52:38,837 INFO L93 Difference]: Finished difference Result 138 states and 192 transitions. [2022-04-05 06:52:38,838 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-04-05 06:52:38,838 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.3) internal successors, (33), 10 states have internal predecessors, (33), 4 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) Word has length 24 [2022-04-05 06:52:38,838 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 06:52:38,840 INFO L225 Difference]: With dead ends: 138 [2022-04-05 06:52:38,840 INFO L226 Difference]: Without dead ends: 129 [2022-04-05 06:52:38,841 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 39 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=63, Invalid=119, Unknown=0, NotChecked=0, Total=182 [2022-04-05 06:52:38,841 INFO L913 BasicCegarLoop]: 78 mSDtfsCounter, 154 mSDsluCounter, 178 mSDsCounter, 0 mSdLazyCounter, 118 mSolverCounterSat, 78 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 7.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 154 SdHoareTripleChecker+Valid, 256 SdHoareTripleChecker+Invalid, 197 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 78 IncrementalHoareTripleChecker+Valid, 118 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 7.1s IncrementalHoareTripleChecker+Time [2022-04-05 06:52:38,841 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [154 Valid, 256 Invalid, 197 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [78 Valid, 118 Invalid, 1 Unknown, 0 Unchecked, 7.1s Time] [2022-04-05 06:52:38,842 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 129 states. [2022-04-05 06:52:38,857 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 129 to 120. [2022-04-05 06:52:38,857 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 120 states, 65 states have (on average 1.3384615384615384) internal successors, (87), 70 states have internal predecessors, (87), 46 states have call successors, (46), 9 states have call predecessors, (46), 8 states have return successors, (40), 40 states have call predecessors, (40), 40 states have call successors, (40) [2022-04-05 06:52:38,858 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 120 states to 120 states and 173 transitions. [2022-04-05 06:52:38,858 INFO L78 Accepts]: Start accepts. Automaton has 120 states and 173 transitions. Word has length 24 [2022-04-05 06:52:38,859 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 06:52:38,859 INFO L478 AbstractCegarLoop]: Abstraction has 120 states and 173 transitions. [2022-04-05 06:52:38,859 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.3) internal successors, (33), 10 states have internal predecessors, (33), 4 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2022-04-05 06:52:38,859 INFO L276 IsEmpty]: Start isEmpty. Operand 120 states and 173 transitions. [2022-04-05 06:52:38,860 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2022-04-05 06:52:38,860 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 06:52:38,860 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 06:52:38,882 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 06:52:39,071 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 06:52:39,072 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 06:52:39,072 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 06:52:39,072 INFO L85 PathProgramCache]: Analyzing trace with hash -1729947946, now seen corresponding path program 1 times [2022-04-05 06:52:39,072 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 06:52:39,072 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [980548828] [2022-04-05 06:52:39,073 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:52:39,073 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 06:52:39,091 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:52:39,217 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-05 06:52:39,223 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:52:39,233 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-05 06:52:39,234 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:52:39,239 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 06:52:39,240 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 06:52:39,240 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [980548828] [2022-04-05 06:52:39,240 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [980548828] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-05 06:52:39,240 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1333957397] [2022-04-05 06:52:39,240 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:52:39,240 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 06:52:39,240 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 06:52:39,249 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 06:52:39,250 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 06:52:39,289 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:52:39,290 INFO L263 TraceCheckSpWp]: Trace formula consists of 94 conjuncts, 12 conjunts are in the unsatisfiable core [2022-04-05 06:52:39,291 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 06:52:39,436 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 06:52:39,436 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 06:52:39,567 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 06:52:39,567 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1333957397] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 06:52:39,568 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-04-05 06:52:39,568 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7, 7] total 15 [2022-04-05 06:52:39,568 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [292620845] [2022-04-05 06:52:39,568 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-04-05 06:52:39,568 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-04-05 06:52:39,568 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 06:52:39,569 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-04-05 06:52:39,569 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=44, Invalid=166, Unknown=0, NotChecked=0, Total=210 [2022-04-05 06:52:39,569 INFO L87 Difference]: Start difference. First operand 120 states and 173 transitions. Second operand has 15 states, 15 states have (on average 2.4) internal successors, (36), 12 states have internal predecessors, (36), 4 states have call successors, (7), 4 states have call predecessors, (7), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-05 06:52:44,506 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-05 06:52:46,544 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-05 06:52:49,360 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-05 06:52:51,944 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.10s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-05 06:52:55,368 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-05 06:52:56,910 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.02s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 06:53:01,437 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-05 06:53:03,443 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-05 06:53:05,550 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-05 06:53:07,922 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 06:53:07,922 INFO L93 Difference]: Finished difference Result 194 states and 284 transitions. [2022-04-05 06:53:07,922 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-04-05 06:53:07,923 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.4) internal successors, (36), 12 states have internal predecessors, (36), 4 states have call successors, (7), 4 states have call predecessors, (7), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 24 [2022-04-05 06:53:07,923 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 06:53:07,924 INFO L225 Difference]: With dead ends: 194 [2022-04-05 06:53:07,924 INFO L226 Difference]: Without dead ends: 177 [2022-04-05 06:53:07,925 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 43 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 75 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=95, Invalid=367, Unknown=0, NotChecked=0, Total=462 [2022-04-05 06:53:07,925 INFO L913 BasicCegarLoop]: 59 mSDtfsCounter, 46 mSDsluCounter, 130 mSDsCounter, 0 mSdLazyCounter, 606 mSolverCounterSat, 121 mSolverCounterUnsat, 7 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 28.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 55 SdHoareTripleChecker+Valid, 189 SdHoareTripleChecker+Invalid, 734 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 121 IncrementalHoareTripleChecker+Valid, 606 IncrementalHoareTripleChecker+Invalid, 7 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 28.2s IncrementalHoareTripleChecker+Time [2022-04-05 06:53:07,925 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [55 Valid, 189 Invalid, 734 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [121 Valid, 606 Invalid, 7 Unknown, 0 Unchecked, 28.2s Time] [2022-04-05 06:53:07,926 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 177 states. [2022-04-05 06:53:07,946 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 177 to 170. [2022-04-05 06:53:07,946 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 170 states, 92 states have (on average 1.2826086956521738) internal successors, (118), 100 states have internal predecessors, (118), 65 states have call successors, (65), 13 states have call predecessors, (65), 12 states have return successors, (57), 56 states have call predecessors, (57), 57 states have call successors, (57) [2022-04-05 06:53:07,948 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 170 states to 170 states and 240 transitions. [2022-04-05 06:53:07,948 INFO L78 Accepts]: Start accepts. Automaton has 170 states and 240 transitions. Word has length 24 [2022-04-05 06:53:07,948 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 06:53:07,948 INFO L478 AbstractCegarLoop]: Abstraction has 170 states and 240 transitions. [2022-04-05 06:53:07,948 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.4) internal successors, (36), 12 states have internal predecessors, (36), 4 states have call successors, (7), 4 states have call predecessors, (7), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-05 06:53:07,948 INFO L276 IsEmpty]: Start isEmpty. Operand 170 states and 240 transitions. [2022-04-05 06:53:07,949 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2022-04-05 06:53:07,949 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 06:53:07,949 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 06:53:07,966 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 06:53:08,155 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 06:53:08,155 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 06:53:08,156 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 06:53:08,156 INFO L85 PathProgramCache]: Analyzing trace with hash -2026335537, now seen corresponding path program 1 times [2022-04-05 06:53:08,156 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 06:53:08,156 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1087509599] [2022-04-05 06:53:08,156 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:53:08,156 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 06:53:08,162 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 06:53:08,163 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1075964843] [2022-04-05 06:53:08,163 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:53:08,163 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 06:53:08,163 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 06:53:08,163 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 06:53:08,164 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 06:53:08,255 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:53:08,256 INFO L263 TraceCheckSpWp]: Trace formula consists of 104 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-05 06:53:08,257 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 06:53:08,371 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 06:53:08,371 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-05 06:53:08,372 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 06:53:08,372 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1087509599] [2022-04-05 06:53:08,372 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 06:53:08,372 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1075964843] [2022-04-05 06:53:08,372 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1075964843] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 06:53:08,372 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 06:53:08,372 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-05 06:53:08,372 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1160399632] [2022-04-05 06:53:08,373 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 06:53:08,374 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-05 06:53:08,374 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 06:53:08,374 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-05 06:53:08,375 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-05 06:53:08,375 INFO L87 Difference]: Start difference. First operand 170 states and 240 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-05 06:53:10,711 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 06:53:10,741 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 06:53:10,741 INFO L93 Difference]: Finished difference Result 176 states and 244 transitions. [2022-04-05 06:53:10,741 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-05 06:53:10,742 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 31 [2022-04-05 06:53:10,742 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 06:53:10,744 INFO L225 Difference]: With dead ends: 176 [2022-04-05 06:53:10,745 INFO L226 Difference]: Without dead ends: 152 [2022-04-05 06:53:10,745 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 31 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-05 06:53:10,745 INFO L913 BasicCegarLoop]: 49 mSDtfsCounter, 6 mSDsluCounter, 105 mSDsCounter, 0 mSdLazyCounter, 55 mSolverCounterSat, 2 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 154 SdHoareTripleChecker+Invalid, 58 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 55 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.3s IncrementalHoareTripleChecker+Time [2022-04-05 06:53:10,746 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 154 Invalid, 58 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 55 Invalid, 1 Unknown, 0 Unchecked, 2.3s Time] [2022-04-05 06:53:10,747 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 152 states. [2022-04-05 06:53:10,759 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 152 to 152. [2022-04-05 06:53:10,759 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 152 states, 83 states have (on average 1.2891566265060241) internal successors, (107), 90 states have internal predecessors, (107), 58 states have call successors, (58), 11 states have call predecessors, (58), 10 states have return successors, (51), 50 states have call predecessors, (51), 51 states have call successors, (51) [2022-04-05 06:53:10,761 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 152 states to 152 states and 216 transitions. [2022-04-05 06:53:10,761 INFO L78 Accepts]: Start accepts. Automaton has 152 states and 216 transitions. Word has length 31 [2022-04-05 06:53:10,761 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 06:53:10,761 INFO L478 AbstractCegarLoop]: Abstraction has 152 states and 216 transitions. [2022-04-05 06:53:10,761 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-05 06:53:10,761 INFO L276 IsEmpty]: Start isEmpty. Operand 152 states and 216 transitions. [2022-04-05 06:53:10,762 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2022-04-05 06:53:10,762 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 06:53:10,762 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 06:53:10,771 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 06:53:10,966 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 06:53:10,966 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 06:53:10,966 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 06:53:10,967 INFO L85 PathProgramCache]: Analyzing trace with hash -266035918, now seen corresponding path program 1 times [2022-04-05 06:53:10,967 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 06:53:10,967 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [125338730] [2022-04-05 06:53:10,967 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:53:10,967 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 06:53:10,977 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 06:53:10,980 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [508282260] [2022-04-05 06:53:10,980 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:53:10,980 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 06:53:10,980 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 06:53:10,981 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 06:53:10,981 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 06:53:11,046 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:53:11,049 INFO L263 TraceCheckSpWp]: Trace formula consists of 112 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-05 06:53:11,051 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 06:53:11,127 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2022-04-05 06:53:11,127 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-05 06:53:11,127 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 06:53:11,127 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [125338730] [2022-04-05 06:53:11,127 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 06:53:11,127 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [508282260] [2022-04-05 06:53:11,127 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [508282260] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 06:53:11,127 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 06:53:11,128 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-05 06:53:11,128 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1883518022] [2022-04-05 06:53:11,128 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 06:53:11,128 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-05 06:53:11,128 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 06:53:11,128 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-05 06:53:11,128 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-05 06:53:11,128 INFO L87 Difference]: Start difference. First operand 152 states and 216 transitions. Second operand has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-05 06:53:13,248 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 06:53:13,331 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 06:53:13,331 INFO L93 Difference]: Finished difference Result 182 states and 241 transitions. [2022-04-05 06:53:13,331 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-05 06:53:13,331 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 34 [2022-04-05 06:53:13,332 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 06:53:13,332 INFO L225 Difference]: With dead ends: 182 [2022-04-05 06:53:13,332 INFO L226 Difference]: Without dead ends: 177 [2022-04-05 06:53:13,333 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-05 06:53:13,333 INFO L913 BasicCegarLoop]: 50 mSDtfsCounter, 8 mSDsluCounter, 106 mSDsCounter, 0 mSdLazyCounter, 45 mSolverCounterSat, 2 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 156 SdHoareTripleChecker+Invalid, 48 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 45 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.2s IncrementalHoareTripleChecker+Time [2022-04-05 06:53:13,333 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 156 Invalid, 48 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 45 Invalid, 1 Unknown, 0 Unchecked, 2.2s Time] [2022-04-05 06:53:13,334 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 177 states. [2022-04-05 06:53:13,353 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 177 to 170. [2022-04-05 06:53:13,353 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 170 states, 97 states have (on average 1.1649484536082475) internal successors, (113), 101 states have internal predecessors, (113), 55 states have call successors, (55), 18 states have call predecessors, (55), 17 states have return successors, (51), 50 states have call predecessors, (51), 51 states have call successors, (51) [2022-04-05 06:53:13,354 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 170 states to 170 states and 219 transitions. [2022-04-05 06:53:13,354 INFO L78 Accepts]: Start accepts. Automaton has 170 states and 219 transitions. Word has length 34 [2022-04-05 06:53:13,354 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 06:53:13,354 INFO L478 AbstractCegarLoop]: Abstraction has 170 states and 219 transitions. [2022-04-05 06:53:13,355 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-05 06:53:13,355 INFO L276 IsEmpty]: Start isEmpty. Operand 170 states and 219 transitions. [2022-04-05 06:53:13,355 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2022-04-05 06:53:13,355 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 06:53:13,355 INFO L499 BasicCegarLoop]: trace histogram [5, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 06:53:13,362 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 06:53:13,556 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 06:53:13,556 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 06:53:13,557 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 06:53:13,557 INFO L85 PathProgramCache]: Analyzing trace with hash 1209382940, now seen corresponding path program 1 times [2022-04-05 06:53:13,557 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 06:53:13,557 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1593714629] [2022-04-05 06:53:13,557 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:53:13,557 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 06:53:13,568 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:53:13,638 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-05 06:53:13,640 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:53:13,645 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-05 06:53:13,646 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:53:13,648 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 06:53:13,648 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 06:53:13,648 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1593714629] [2022-04-05 06:53:13,649 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1593714629] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-05 06:53:13,649 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [50709648] [2022-04-05 06:53:13,649 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:53:13,649 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 06:53:13,649 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 06:53:13,651 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 06:53:13,673 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 06:53:13,687 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:53:13,688 INFO L263 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 13 conjunts are in the unsatisfiable core [2022-04-05 06:53:13,689 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 06:53:13,766 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 06:53:13,766 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 06:53:13,918 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 06:53:13,919 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [50709648] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 06:53:13,919 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-04-05 06:53:13,919 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8, 8] total 15 [2022-04-05 06:53:13,919 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [97575223] [2022-04-05 06:53:13,919 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-04-05 06:53:13,919 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-04-05 06:53:13,920 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 06:53:13,920 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-04-05 06:53:13,920 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=73, Invalid=137, Unknown=0, NotChecked=0, Total=210 [2022-04-05 06:53:13,920 INFO L87 Difference]: Start difference. First operand 170 states and 219 transitions. Second operand has 15 states, 15 states have (on average 3.2) internal successors, (48), 14 states have internal predecessors, (48), 4 states have call successors, (8), 5 states have call predecessors, (8), 3 states have return successors, (5), 2 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-05 06:53:16,200 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 06:53:19,049 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 06:53:21,462 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-05 06:53:24,163 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-05 06:53:26,261 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-05 06:53:27,585 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.16s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-05 06:53:30,573 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 06:53:37,119 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-05 06:53:39,124 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-05 06:53:41,071 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.37s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-05 06:53:46,158 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 06:53:47,469 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 06:53:47,469 INFO L93 Difference]: Finished difference Result 342 states and 438 transitions. [2022-04-05 06:53:47,470 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2022-04-05 06:53:47,470 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 3.2) internal successors, (48), 14 states have internal predecessors, (48), 4 states have call successors, (8), 5 states have call predecessors, (8), 3 states have return successors, (5), 2 states have call predecessors, (5), 3 states have call successors, (5) Word has length 32 [2022-04-05 06:53:47,470 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 06:53:47,471 INFO L225 Difference]: With dead ends: 342 [2022-04-05 06:53:47,471 INFO L226 Difference]: Without dead ends: 302 [2022-04-05 06:53:47,472 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 93 GetRequests, 63 SyntacticMatches, 0 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 165 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=276, Invalid=716, Unknown=0, NotChecked=0, Total=992 [2022-04-05 06:53:47,472 INFO L913 BasicCegarLoop]: 52 mSDtfsCounter, 172 mSDsluCounter, 164 mSDsCounter, 0 mSdLazyCounter, 465 mSolverCounterSat, 101 mSolverCounterUnsat, 9 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 33.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 206 SdHoareTripleChecker+Valid, 216 SdHoareTripleChecker+Invalid, 575 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 101 IncrementalHoareTripleChecker+Valid, 465 IncrementalHoareTripleChecker+Invalid, 9 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 33.3s IncrementalHoareTripleChecker+Time [2022-04-05 06:53:47,473 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [206 Valid, 216 Invalid, 575 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [101 Valid, 465 Invalid, 9 Unknown, 0 Unchecked, 33.3s Time] [2022-04-05 06:53:47,473 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 302 states. [2022-04-05 06:53:47,489 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 302 to 258. [2022-04-05 06:53:47,489 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 258 states, 153 states have (on average 1.1830065359477124) internal successors, (181), 160 states have internal predecessors, (181), 78 states have call successors, (78), 27 states have call predecessors, (78), 26 states have return successors, (73), 70 states have call predecessors, (73), 73 states have call successors, (73) [2022-04-05 06:53:47,491 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 258 states to 258 states and 332 transitions. [2022-04-05 06:53:47,491 INFO L78 Accepts]: Start accepts. Automaton has 258 states and 332 transitions. Word has length 32 [2022-04-05 06:53:47,491 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 06:53:47,491 INFO L478 AbstractCegarLoop]: Abstraction has 258 states and 332 transitions. [2022-04-05 06:53:47,491 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 3.2) internal successors, (48), 14 states have internal predecessors, (48), 4 states have call successors, (8), 5 states have call predecessors, (8), 3 states have return successors, (5), 2 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-05 06:53:47,491 INFO L276 IsEmpty]: Start isEmpty. Operand 258 states and 332 transitions. [2022-04-05 06:53:47,493 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2022-04-05 06:53:47,493 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 06:53:47,493 INFO L499 BasicCegarLoop]: trace histogram [11, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 06:53:47,513 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 06:53:47,693 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2022-04-05 06:53:47,693 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 06:53:47,694 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 06:53:47,694 INFO L85 PathProgramCache]: Analyzing trace with hash -1556551492, now seen corresponding path program 2 times [2022-04-05 06:53:47,694 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 06:53:47,694 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [839560708] [2022-04-05 06:53:47,694 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:53:47,694 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 06:53:47,710 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:53:47,741 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-05 06:53:47,742 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:53:47,746 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-05 06:53:47,747 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:53:47,750 INFO L134 CoverageAnalysis]: Checked inductivity of 155 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 145 trivial. 0 not checked. [2022-04-05 06:53:47,750 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 06:53:47,750 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [839560708] [2022-04-05 06:53:47,751 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [839560708] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 06:53:47,751 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 06:53:47,751 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-05 06:53:47,751 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [841870316] [2022-04-05 06:53:47,751 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 06:53:47,752 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-05 06:53:47,752 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 06:53:47,752 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-05 06:53:47,752 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-04-05 06:53:47,752 INFO L87 Difference]: Start difference. First operand 258 states and 332 transitions. Second operand has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-05 06:53:49,863 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.02s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-05 06:53:52,314 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-05 06:53:54,320 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-05 06:53:56,322 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-05 06:53:56,334 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 06:53:56,334 INFO L93 Difference]: Finished difference Result 295 states and 381 transitions. [2022-04-05 06:53:56,334 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-05 06:53:56,334 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 50 [2022-04-05 06:53:56,334 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 06:53:56,335 INFO L225 Difference]: With dead ends: 295 [2022-04-05 06:53:56,336 INFO L226 Difference]: Without dead ends: 255 [2022-04-05 06:53:56,336 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-04-05 06:53:56,336 INFO L913 BasicCegarLoop]: 42 mSDtfsCounter, 10 mSDsluCounter, 64 mSDsCounter, 0 mSdLazyCounter, 99 mSolverCounterSat, 12 mSolverCounterUnsat, 3 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 8.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 106 SdHoareTripleChecker+Invalid, 114 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 99 IncrementalHoareTripleChecker+Invalid, 3 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 8.6s IncrementalHoareTripleChecker+Time [2022-04-05 06:53:56,337 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 106 Invalid, 114 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 99 Invalid, 3 Unknown, 0 Unchecked, 8.6s Time] [2022-04-05 06:53:56,337 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 255 states. [2022-04-05 06:53:56,349 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 255 to 206. [2022-04-05 06:53:56,350 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 206 states, 121 states have (on average 1.165289256198347) internal successors, (141), 126 states have internal predecessors, (141), 62 states have call successors, (62), 23 states have call predecessors, (62), 22 states have return successors, (58), 56 states have call predecessors, (58), 58 states have call successors, (58) [2022-04-05 06:53:56,351 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 206 states to 206 states and 261 transitions. [2022-04-05 06:53:56,351 INFO L78 Accepts]: Start accepts. Automaton has 206 states and 261 transitions. Word has length 50 [2022-04-05 06:53:56,352 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 06:53:56,352 INFO L478 AbstractCegarLoop]: Abstraction has 206 states and 261 transitions. [2022-04-05 06:53:56,353 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-05 06:53:56,353 INFO L276 IsEmpty]: Start isEmpty. Operand 206 states and 261 transitions. [2022-04-05 06:53:56,358 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2022-04-05 06:53:56,358 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 06:53:56,358 INFO L499 BasicCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 06:53:56,359 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10 [2022-04-05 06:53:56,359 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 06:53:56,359 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 06:53:56,359 INFO L85 PathProgramCache]: Analyzing trace with hash -926681017, now seen corresponding path program 1 times [2022-04-05 06:53:56,359 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 06:53:56,359 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [464765692] [2022-04-05 06:53:56,359 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:53:56,359 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 06:53:56,376 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 06:53:56,376 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [505983475] [2022-04-05 06:53:56,376 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:53:56,376 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 06:53:56,376 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 06:53:56,377 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 06:53:56,378 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process