/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/AutomizerC.xml -s ../../../trunk/examples/settings/default/automizer/svcomp-Reach-32bit-Automizer_Default.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/egcd2-ll_valuebound20.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-b030c9e [2022-03-20 00:40:45,430 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-03-20 00:40:45,431 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-03-20 00:40:45,453 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-03-20 00:40:45,453 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-03-20 00:40:45,455 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-03-20 00:40:45,458 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-03-20 00:40:45,464 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-03-20 00:40:45,465 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-03-20 00:40:45,469 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-03-20 00:40:45,470 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-03-20 00:40:45,471 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-03-20 00:40:45,471 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-03-20 00:40:45,473 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-03-20 00:40:45,474 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-03-20 00:40:45,474 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-03-20 00:40:45,475 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-03-20 00:40:45,475 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-03-20 00:40:45,479 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-03-20 00:40:45,485 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-03-20 00:40:45,486 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-03-20 00:40:45,487 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-03-20 00:40:45,488 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-03-20 00:40:45,488 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-03-20 00:40:45,490 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-03-20 00:40:45,494 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-03-20 00:40:45,495 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-03-20 00:40:45,495 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-03-20 00:40:45,496 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-03-20 00:40:45,496 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-03-20 00:40:45,497 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-03-20 00:40:45,497 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-03-20 00:40:45,498 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-03-20 00:40:45,499 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-03-20 00:40:45,499 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-03-20 00:40:45,500 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-03-20 00:40:45,500 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-03-20 00:40:45,500 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-03-20 00:40:45,500 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-03-20 00:40:45,500 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-03-20 00:40:45,501 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-03-20 00:40:45,502 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-03-20 00:40:45,503 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/default/automizer/svcomp-Reach-32bit-Automizer_Default.epf [2022-03-20 00:40:45,528 INFO L113 SettingsManager]: Loading preferences was successful [2022-03-20 00:40:45,528 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-03-20 00:40:45,529 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2022-03-20 00:40:45,529 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2022-03-20 00:40:45,529 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-03-20 00:40:45,529 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-03-20 00:40:45,530 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-03-20 00:40:45,530 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-03-20 00:40:45,530 INFO L138 SettingsManager]: * Use SBE=true [2022-03-20 00:40:45,530 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-03-20 00:40:45,530 INFO L138 SettingsManager]: * sizeof long=4 [2022-03-20 00:40:45,530 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-03-20 00:40:45,530 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-03-20 00:40:45,530 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-03-20 00:40:45,530 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-03-20 00:40:45,530 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-03-20 00:40:45,530 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-03-20 00:40:45,530 INFO L138 SettingsManager]: * sizeof long double=12 [2022-03-20 00:40:45,531 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-03-20 00:40:45,531 INFO L138 SettingsManager]: * Use constant arrays=true [2022-03-20 00:40:45,531 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-03-20 00:40:45,532 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-03-20 00:40:45,532 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-03-20 00:40:45,532 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-03-20 00:40:45,532 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-20 00:40:45,532 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-03-20 00:40:45,532 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-03-20 00:40:45,533 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-03-20 00:40:45,533 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-03-20 00:40:45,533 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-03-20 00:40:45,533 INFO L138 SettingsManager]: * Large block encoding in concurrent analysis=OFF [2022-03-20 00:40:45,533 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2022-03-20 00:40:45,533 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-03-20 00:40:45,533 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-03-20 00:40:45,710 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-03-20 00:40:45,730 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-03-20 00:40:45,731 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-03-20 00:40:45,732 INFO L271 PluginConnector]: Initializing CDTParser... [2022-03-20 00:40:45,739 INFO L275 PluginConnector]: CDTParser initialized [2022-03-20 00:40:45,741 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/egcd2-ll_valuebound20.c [2022-03-20 00:40:45,809 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/d37a14ecf/1f51995c5de642a39a8fb994588e6f28/FLAG6a2f9dff5 [2022-03-20 00:40:46,107 INFO L306 CDTParser]: Found 1 translation units. [2022-03-20 00:40:46,108 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/egcd2-ll_valuebound20.c [2022-03-20 00:40:46,116 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/d37a14ecf/1f51995c5de642a39a8fb994588e6f28/FLAG6a2f9dff5 [2022-03-20 00:40:46,537 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/d37a14ecf/1f51995c5de642a39a8fb994588e6f28 [2022-03-20 00:40:46,539 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-03-20 00:40:46,541 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-03-20 00:40:46,544 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-03-20 00:40:46,545 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-03-20 00:40:46,547 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-03-20 00:40:46,548 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.03 12:40:46" (1/1) ... [2022-03-20 00:40:46,549 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@10992c50 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 12:40:46, skipping insertion in model container [2022-03-20 00:40:46,550 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.03 12:40:46" (1/1) ... [2022-03-20 00:40:46,554 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-03-20 00:40:46,569 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-03-20 00:40:46,696 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/egcd2-ll_valuebound20.c[490,503] [2022-03-20 00:40:46,729 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-20 00:40:46,735 INFO L203 MainTranslator]: Completed pre-run [2022-03-20 00:40:46,751 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/egcd2-ll_valuebound20.c[490,503] [2022-03-20 00:40:46,781 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-20 00:40:46,792 INFO L208 MainTranslator]: Completed translation [2022-03-20 00:40:46,793 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 12:40:46 WrapperNode [2022-03-20 00:40:46,793 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-03-20 00:40:46,794 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-03-20 00:40:46,794 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-03-20 00:40:46,794 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-03-20 00:40:46,802 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 12:40:46" (1/1) ... [2022-03-20 00:40:46,802 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 12:40:46" (1/1) ... [2022-03-20 00:40:46,820 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 12:40:46" (1/1) ... [2022-03-20 00:40:46,821 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 12:40:46" (1/1) ... [2022-03-20 00:40:46,828 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 12:40:46" (1/1) ... [2022-03-20 00:40:46,831 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 12:40:46" (1/1) ... [2022-03-20 00:40:46,832 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 12:40:46" (1/1) ... [2022-03-20 00:40:46,834 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-03-20 00:40:46,834 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-03-20 00:40:46,834 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-03-20 00:40:46,834 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-03-20 00:40:46,840 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 12:40:46" (1/1) ... [2022-03-20 00:40:46,845 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-20 00:40:46,852 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 00:40:46,862 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-03-20 00:40:46,867 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-03-20 00:40:46,888 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-03-20 00:40:46,888 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-03-20 00:40:46,888 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-03-20 00:40:46,888 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-03-20 00:40:46,888 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-03-20 00:40:46,888 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-03-20 00:40:46,889 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-03-20 00:40:46,889 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-03-20 00:40:46,889 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-03-20 00:40:46,889 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-03-20 00:40:46,889 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-03-20 00:40:46,889 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-03-20 00:40:46,889 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-03-20 00:40:46,889 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-03-20 00:40:46,889 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-03-20 00:40:46,889 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-03-20 00:40:46,890 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-03-20 00:40:46,890 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-03-20 00:40:46,890 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-03-20 00:40:46,890 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-03-20 00:40:46,936 INFO L234 CfgBuilder]: Building ICFG [2022-03-20 00:40:46,937 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-03-20 00:40:47,067 INFO L275 CfgBuilder]: Performing block encoding [2022-03-20 00:40:47,072 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-03-20 00:40:47,072 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-03-20 00:40:47,074 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 12:40:47 BoogieIcfgContainer [2022-03-20 00:40:47,074 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-03-20 00:40:47,077 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-03-20 00:40:47,077 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-03-20 00:40:47,080 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-03-20 00:40:47,080 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 20.03 12:40:46" (1/3) ... [2022-03-20 00:40:47,080 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5ac52637 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.03 12:40:47, skipping insertion in model container [2022-03-20 00:40:47,080 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 12:40:46" (2/3) ... [2022-03-20 00:40:47,086 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5ac52637 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.03 12:40:47, skipping insertion in model container [2022-03-20 00:40:47,086 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 12:40:47" (3/3) ... [2022-03-20 00:40:47,087 INFO L111 eAbstractionObserver]: Analyzing ICFG egcd2-ll_valuebound20.c [2022-03-20 00:40:47,091 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-03-20 00:40:47,091 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-03-20 00:40:47,135 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-03-20 00:40:47,140 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=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP [2022-03-20 00:40:47,140 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-03-20 00:40:47,153 INFO L276 IsEmpty]: Start isEmpty. Operand has 40 states, 20 states have (on average 1.45) internal successors, (29), 22 states have internal predecessors, (29), 14 states have call successors, (14), 4 states have call predecessors, (14), 4 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2022-03-20 00:40:47,163 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2022-03-20 00:40:47,163 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 00:40:47,164 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 00:40:47,164 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 00:40:47,168 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 00:40:47,168 INFO L85 PathProgramCache]: Analyzing trace with hash -587582002, now seen corresponding path program 1 times [2022-03-20 00:40:47,174 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 00:40:47,175 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [473744176] [2022-03-20 00:40:47,175 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 00:40:47,175 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 00:40:47,265 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 00:40:47,335 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-20 00:40:47,341 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 00:40:47,349 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-20 00:40:47,354 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 00:40:47,369 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-03-20 00:40:47,371 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 00:40:47,380 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-03-20 00:40:47,382 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 00:40:47,388 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2022-03-20 00:40:47,389 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 00:40:47,397 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2022-03-20 00:40:47,401 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 00:40:47,405 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 33 [2022-03-20 00:40:47,409 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 00:40:47,416 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-03-20 00:40:47,417 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 00:40:47,417 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [473744176] [2022-03-20 00:40:47,418 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [473744176] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 00:40:47,418 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 00:40:47,418 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-20 00:40:47,419 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [701602796] [2022-03-20 00:40:47,420 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 00:40:47,426 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-03-20 00:40:47,426 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 00:40:47,450 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-03-20 00:40:47,451 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-20 00:40:47,452 INFO L87 Difference]: Start difference. First operand has 40 states, 20 states have (on average 1.45) internal successors, (29), 22 states have internal predecessors, (29), 14 states have call successors, (14), 4 states have call predecessors, (14), 4 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) 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, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-03-20 00:40:47,565 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 00:40:47,565 INFO L93 Difference]: Finished difference Result 73 states and 118 transitions. [2022-03-20 00:40:47,567 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-03-20 00:40:47,568 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, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 43 [2022-03-20 00:40:47,568 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 00:40:47,574 INFO L225 Difference]: With dead ends: 73 [2022-03-20 00:40:47,574 INFO L226 Difference]: Without dead ends: 35 [2022-03-20 00:40:47,578 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-20 00:40:47,582 INFO L913 BasicCegarLoop]: 39 mSDtfsCounter, 20 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 14 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 42 SdHoareTripleChecker+Invalid, 27 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 14 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 00:40:47,583 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [32 Valid, 42 Invalid, 27 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 14 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 00:40:47,596 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2022-03-20 00:40:47,619 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 35. [2022-03-20 00:40:47,620 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 17 states have (on average 1.1764705882352942) internal successors, (20), 19 states have internal predecessors, (20), 14 states have call successors, (14), 4 states have call predecessors, (14), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-03-20 00:40:47,621 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 46 transitions. [2022-03-20 00:40:47,622 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 46 transitions. Word has length 43 [2022-03-20 00:40:47,622 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 00:40:47,623 INFO L478 AbstractCegarLoop]: Abstraction has 35 states and 46 transitions. [2022-03-20 00:40:47,623 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, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-03-20 00:40:47,623 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 46 transitions. [2022-03-20 00:40:47,624 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2022-03-20 00:40:47,624 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 00:40:47,625 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 00:40:47,625 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-03-20 00:40:47,625 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 00:40:47,626 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 00:40:47,626 INFO L85 PathProgramCache]: Analyzing trace with hash 987777007, now seen corresponding path program 1 times [2022-03-20 00:40:47,626 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 00:40:47,626 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1327687566] [2022-03-20 00:40:47,626 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 00:40:47,626 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 00:40:47,642 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 00:40:47,642 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1792376287] [2022-03-20 00:40:47,642 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 00:40:47,643 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 00:40:47,643 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 00:40:47,644 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 00:40:47,645 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-03-20 00:40:47,698 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 00:40:47,700 INFO L263 TraceCheckSpWp]: Trace formula consists of 133 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-20 00:40:47,710 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 00:40:47,848 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 9 proven. 6 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-03-20 00:40:47,848 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 00:40:47,960 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 9 proven. 6 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-03-20 00:40:47,961 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 00:40:47,961 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1327687566] [2022-03-20 00:40:47,961 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 00:40:47,961 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1792376287] [2022-03-20 00:40:47,961 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1792376287] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 00:40:47,962 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 00:40:47,962 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2022-03-20 00:40:47,962 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1131351989] [2022-03-20 00:40:47,962 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 00:40:47,963 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-03-20 00:40:47,963 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 00:40:47,963 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-03-20 00:40:47,964 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-03-20 00:40:47,965 INFO L87 Difference]: Start difference. First operand 35 states and 46 transitions. Second operand has 7 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) [2022-03-20 00:40:48,080 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 00:40:48,080 INFO L93 Difference]: Finished difference Result 52 states and 69 transitions. [2022-03-20 00:40:48,081 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-03-20 00:40:48,081 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) Word has length 44 [2022-03-20 00:40:48,081 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 00:40:48,084 INFO L225 Difference]: With dead ends: 52 [2022-03-20 00:40:48,084 INFO L226 Difference]: Without dead ends: 44 [2022-03-20 00:40:48,084 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 89 GetRequests, 81 SyntacticMatches, 1 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2022-03-20 00:40:48,086 INFO L913 BasicCegarLoop]: 38 mSDtfsCounter, 19 mSDsluCounter, 146 mSDsCounter, 0 mSdLazyCounter, 81 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 184 SdHoareTripleChecker+Invalid, 92 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 81 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 00:40:48,086 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 184 Invalid, 92 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 81 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 00:40:48,088 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2022-03-20 00:40:48,098 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 37. [2022-03-20 00:40:48,098 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 19 states have (on average 1.1578947368421053) internal successors, (22), 20 states have internal predecessors, (22), 14 states have call successors, (14), 4 states have call predecessors, (14), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-03-20 00:40:48,099 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 48 transitions. [2022-03-20 00:40:48,099 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 48 transitions. Word has length 44 [2022-03-20 00:40:48,099 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 00:40:48,099 INFO L478 AbstractCegarLoop]: Abstraction has 37 states and 48 transitions. [2022-03-20 00:40:48,099 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) [2022-03-20 00:40:48,100 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 48 transitions. [2022-03-20 00:40:48,100 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2022-03-20 00:40:48,100 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 00:40:48,101 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 00:40:48,121 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-03-20 00:40:48,314 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 00:40:48,315 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 00:40:48,315 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 00:40:48,315 INFO L85 PathProgramCache]: Analyzing trace with hash 561616070, now seen corresponding path program 1 times [2022-03-20 00:40:48,316 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 00:40:48,316 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1901854174] [2022-03-20 00:40:48,316 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 00:40:48,316 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 00:40:48,331 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 00:40:48,332 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2124856309] [2022-03-20 00:40:48,332 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 00:40:48,332 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 00:40:48,332 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 00:40:48,333 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 00:40:48,334 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-03-20 00:40:48,375 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 00:40:48,376 INFO L263 TraceCheckSpWp]: Trace formula consists of 137 conjuncts, 14 conjunts are in the unsatisfiable core [2022-03-20 00:40:48,379 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 00:40:48,513 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 9 proven. 6 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-03-20 00:40:48,513 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 00:40:48,628 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-03-20 00:40:48,628 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 00:40:48,628 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1901854174] [2022-03-20 00:40:48,628 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 00:40:48,628 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2124856309] [2022-03-20 00:40:48,629 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2124856309] provided 1 perfect and 1 imperfect interpolant sequences [2022-03-20 00:40:48,629 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-03-20 00:40:48,629 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2022-03-20 00:40:48,629 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1458449093] [2022-03-20 00:40:48,629 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 00:40:48,629 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 00:40:48,629 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 00:40:48,630 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 00:40:48,630 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=71, Unknown=0, NotChecked=0, Total=90 [2022-03-20 00:40:48,630 INFO L87 Difference]: Start difference. First operand 37 states and 48 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 1 states have call predecessors, (7), 1 states have call successors, (7) [2022-03-20 00:40:48,662 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 00:40:48,662 INFO L93 Difference]: Finished difference Result 43 states and 53 transitions. [2022-03-20 00:40:48,663 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 00:40:48,664 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 1 states have call predecessors, (7), 1 states have call successors, (7) Word has length 45 [2022-03-20 00:40:48,664 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 00:40:48,665 INFO L225 Difference]: With dead ends: 43 [2022-03-20 00:40:48,665 INFO L226 Difference]: Without dead ends: 41 [2022-03-20 00:40:48,665 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 90 GetRequests, 80 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2022-03-20 00:40:48,666 INFO L913 BasicCegarLoop]: 40 mSDtfsCounter, 6 mSDsluCounter, 106 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 146 SdHoareTripleChecker+Invalid, 30 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 00:40:48,666 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 146 Invalid, 30 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 00:40:48,666 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2022-03-20 00:40:48,670 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 41. [2022-03-20 00:40:48,671 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 22 states have (on average 1.1363636363636365) internal successors, (25), 23 states have internal predecessors, (25), 14 states have call successors, (14), 5 states have call predecessors, (14), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-03-20 00:40:48,671 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 51 transitions. [2022-03-20 00:40:48,671 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 51 transitions. Word has length 45 [2022-03-20 00:40:48,672 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 00:40:48,672 INFO L478 AbstractCegarLoop]: Abstraction has 41 states and 51 transitions. [2022-03-20 00:40:48,672 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 1 states have call predecessors, (7), 1 states have call successors, (7) [2022-03-20 00:40:48,672 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 51 transitions. [2022-03-20 00:40:48,673 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2022-03-20 00:40:48,673 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 00:40:48,673 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 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, 1] [2022-03-20 00:40:48,691 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-03-20 00:40:48,891 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2022-03-20 00:40:48,895 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 00:40:48,896 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 00:40:48,896 INFO L85 PathProgramCache]: Analyzing trace with hash -680064098, now seen corresponding path program 1 times [2022-03-20 00:40:48,896 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 00:40:48,896 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1432392454] [2022-03-20 00:40:48,896 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 00:40:48,896 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 00:40:48,906 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 00:40:48,907 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1963783274] [2022-03-20 00:40:48,907 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 00:40:48,907 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 00:40:48,907 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 00:40:48,911 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 00:40:48,914 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-03-20 00:40:48,949 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 00:40:48,951 INFO L263 TraceCheckSpWp]: Trace formula consists of 146 conjuncts, 19 conjunts are in the unsatisfiable core [2022-03-20 00:40:48,952 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 00:40:49,120 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 7 proven. 10 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-03-20 00:40:49,121 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 00:40:49,187 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 00:40:49,190 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1432392454] [2022-03-20 00:40:49,190 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 00:40:49,191 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1963783274] [2022-03-20 00:40:49,191 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1963783274] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 00:40:49,191 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 00:40:49,191 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2022-03-20 00:40:49,191 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [735878748] [2022-03-20 00:40:49,191 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-20 00:40:49,191 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-03-20 00:40:49,191 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 00:40:49,192 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-03-20 00:40:49,192 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=88, Unknown=0, NotChecked=0, Total=110 [2022-03-20 00:40:49,192 INFO L87 Difference]: Start difference. First operand 41 states and 51 transitions. Second operand has 10 states, 10 states have (on average 2.0) internal successors, (20), 8 states have internal predecessors, (20), 3 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2022-03-20 00:40:49,326 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 00:40:49,326 INFO L93 Difference]: Finished difference Result 54 states and 68 transitions. [2022-03-20 00:40:49,327 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-03-20 00:40:49,327 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.0) internal successors, (20), 8 states have internal predecessors, (20), 3 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) Word has length 50 [2022-03-20 00:40:49,327 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 00:40:49,328 INFO L225 Difference]: With dead ends: 54 [2022-03-20 00:40:49,328 INFO L226 Difference]: Without dead ends: 52 [2022-03-20 00:40:49,328 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 44 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=37, Invalid=145, Unknown=0, NotChecked=0, Total=182 [2022-03-20 00:40:49,329 INFO L913 BasicCegarLoop]: 30 mSDtfsCounter, 26 mSDsluCounter, 164 mSDsCounter, 0 mSdLazyCounter, 199 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 194 SdHoareTripleChecker+Invalid, 207 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 199 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 00:40:49,329 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [34 Valid, 194 Invalid, 207 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 199 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 00:40:49,329 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2022-03-20 00:40:49,335 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 51. [2022-03-20 00:40:49,335 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 27 states have (on average 1.1481481481481481) internal successors, (31), 28 states have internal predecessors, (31), 18 states have call successors, (18), 6 states have call predecessors, (18), 5 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-03-20 00:40:49,336 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 65 transitions. [2022-03-20 00:40:49,336 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 65 transitions. Word has length 50 [2022-03-20 00:40:49,336 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 00:40:49,336 INFO L478 AbstractCegarLoop]: Abstraction has 51 states and 65 transitions. [2022-03-20 00:40:49,336 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.0) internal successors, (20), 8 states have internal predecessors, (20), 3 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2022-03-20 00:40:49,336 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 65 transitions. [2022-03-20 00:40:49,337 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2022-03-20 00:40:49,337 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 00:40:49,337 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 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, 1, 1, 1, 1, 1, 1] [2022-03-20 00:40:49,354 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-03-20 00:40:49,554 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 00:40:49,555 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 00:40:49,555 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 00:40:49,555 INFO L85 PathProgramCache]: Analyzing trace with hash 606548870, now seen corresponding path program 1 times [2022-03-20 00:40:49,555 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 00:40:49,555 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [424907299] [2022-03-20 00:40:49,555 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 00:40:49,556 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 00:40:49,565 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 00:40:49,565 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1228470181] [2022-03-20 00:40:49,565 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 00:40:49,565 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 00:40:49,565 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 00:40:49,568 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 00:40:49,569 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-03-20 00:40:49,612 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 00:40:49,613 INFO L263 TraceCheckSpWp]: Trace formula consists of 155 conjuncts, 19 conjunts are in the unsatisfiable core [2022-03-20 00:40:49,615 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 00:40:49,811 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 7 proven. 21 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-03-20 00:40:49,811 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 00:40:49,923 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2022-03-20 00:40:49,923 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 00:40:49,923 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [424907299] [2022-03-20 00:40:49,923 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 00:40:49,923 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1228470181] [2022-03-20 00:40:49,923 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1228470181] provided 1 perfect and 1 imperfect interpolant sequences [2022-03-20 00:40:49,923 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-03-20 00:40:49,924 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2022-03-20 00:40:49,924 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1818538293] [2022-03-20 00:40:49,924 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 00:40:49,925 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 00:40:49,925 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 00:40:49,925 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 00:40:49,926 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2022-03-20 00:40:49,926 INFO L87 Difference]: Start difference. First operand 51 states and 65 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2022-03-20 00:40:49,968 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 00:40:49,969 INFO L93 Difference]: Finished difference Result 58 states and 71 transitions. [2022-03-20 00:40:49,969 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 00:40:49,969 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 55 [2022-03-20 00:40:49,969 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 00:40:49,970 INFO L225 Difference]: With dead ends: 58 [2022-03-20 00:40:49,970 INFO L226 Difference]: Without dead ends: 56 [2022-03-20 00:40:49,970 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 110 GetRequests, 100 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2022-03-20 00:40:49,971 INFO L913 BasicCegarLoop]: 46 mSDtfsCounter, 7 mSDsluCounter, 117 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 163 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 00:40:49,971 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [9 Valid, 163 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 00:40:49,971 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2022-03-20 00:40:49,976 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 55. [2022-03-20 00:40:49,977 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 30 states have (on average 1.1333333333333333) internal successors, (34), 31 states have internal predecessors, (34), 18 states have call successors, (18), 7 states have call predecessors, (18), 6 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-03-20 00:40:49,977 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 68 transitions. [2022-03-20 00:40:49,977 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 68 transitions. Word has length 55 [2022-03-20 00:40:49,978 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 00:40:49,978 INFO L478 AbstractCegarLoop]: Abstraction has 55 states and 68 transitions. [2022-03-20 00:40:49,978 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2022-03-20 00:40:49,978 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 68 transitions. [2022-03-20 00:40:49,978 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2022-03-20 00:40:49,978 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 00:40:49,979 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 00:40:49,998 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-03-20 00:40:50,196 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 00:40:50,196 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 00:40:50,197 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 00:40:50,197 INFO L85 PathProgramCache]: Analyzing trace with hash 1584976990, now seen corresponding path program 1 times [2022-03-20 00:40:50,197 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 00:40:50,197 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1719657007] [2022-03-20 00:40:50,197 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 00:40:50,197 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 00:40:50,205 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 00:40:50,206 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1582367685] [2022-03-20 00:40:50,206 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 00:40:50,206 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 00:40:50,206 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 00:40:50,210 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 00:40:50,210 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-03-20 00:40:50,246 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 00:40:50,248 INFO L263 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 23 conjunts are in the unsatisfiable core [2022-03-20 00:40:50,249 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 00:40:50,419 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 10 proven. 2 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2022-03-20 00:40:50,419 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 00:40:50,489 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 00:40:50,489 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1719657007] [2022-03-20 00:40:50,489 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 00:40:50,489 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1582367685] [2022-03-20 00:40:50,489 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1582367685] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 00:40:50,489 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 00:40:50,489 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2022-03-20 00:40:50,489 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [260693430] [2022-03-20 00:40:50,490 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-20 00:40:50,490 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-03-20 00:40:50,490 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 00:40:50,490 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-03-20 00:40:50,490 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2022-03-20 00:40:50,490 INFO L87 Difference]: Start difference. First operand 55 states and 68 transitions. Second operand has 7 states, 7 states have (on average 2.857142857142857) internal successors, (20), 6 states have internal predecessors, (20), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2022-03-20 00:40:50,569 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 00:40:50,569 INFO L93 Difference]: Finished difference Result 62 states and 74 transitions. [2022-03-20 00:40:50,570 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-20 00:40:50,570 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.857142857142857) internal successors, (20), 6 states have internal predecessors, (20), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) Word has length 60 [2022-03-20 00:40:50,570 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 00:40:50,571 INFO L225 Difference]: With dead ends: 62 [2022-03-20 00:40:50,571 INFO L226 Difference]: Without dead ends: 60 [2022-03-20 00:40:50,571 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 66 GetRequests, 56 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=30, Invalid=80, Unknown=0, NotChecked=0, Total=110 [2022-03-20 00:40:50,572 INFO L913 BasicCegarLoop]: 36 mSDtfsCounter, 12 mSDsluCounter, 118 mSDsCounter, 0 mSdLazyCounter, 90 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 154 SdHoareTripleChecker+Invalid, 93 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 90 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 00:40:50,572 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [13 Valid, 154 Invalid, 93 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 90 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 00:40:50,572 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2022-03-20 00:40:50,577 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 59. [2022-03-20 00:40:50,577 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 33 states have (on average 1.121212121212121) internal successors, (37), 34 states have internal predecessors, (37), 18 states have call successors, (18), 8 states have call predecessors, (18), 7 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-03-20 00:40:50,578 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 71 transitions. [2022-03-20 00:40:50,578 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 71 transitions. Word has length 60 [2022-03-20 00:40:50,578 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 00:40:50,578 INFO L478 AbstractCegarLoop]: Abstraction has 59 states and 71 transitions. [2022-03-20 00:40:50,579 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.857142857142857) internal successors, (20), 6 states have internal predecessors, (20), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2022-03-20 00:40:50,579 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 71 transitions. [2022-03-20 00:40:50,579 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2022-03-20 00:40:50,579 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 00:40:50,579 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 5, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 00:40:50,599 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-03-20 00:40:50,782 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 00:40:50,782 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 00:40:50,782 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 00:40:50,783 INFO L85 PathProgramCache]: Analyzing trace with hash -1682830289, now seen corresponding path program 1 times [2022-03-20 00:40:50,783 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 00:40:50,783 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1146423843] [2022-03-20 00:40:50,783 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 00:40:50,783 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 00:40:50,791 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 00:40:50,792 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [705979818] [2022-03-20 00:40:50,792 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 00:40:50,792 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 00:40:50,792 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 00:40:50,803 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 00:40:50,804 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-03-20 00:40:50,841 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 00:40:50,842 INFO L263 TraceCheckSpWp]: Trace formula consists of 191 conjuncts, 9 conjunts are in the unsatisfiable core [2022-03-20 00:40:50,844 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 00:40:50,978 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 14 proven. 11 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2022-03-20 00:40:50,978 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 00:40:51,101 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 14 proven. 11 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2022-03-20 00:40:51,102 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 00:40:51,102 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1146423843] [2022-03-20 00:40:51,102 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 00:40:51,102 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [705979818] [2022-03-20 00:40:51,102 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [705979818] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 00:40:51,102 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 00:40:51,102 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 9 [2022-03-20 00:40:51,102 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [400560554] [2022-03-20 00:40:51,102 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 00:40:51,103 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-03-20 00:40:51,103 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 00:40:51,103 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-03-20 00:40:51,103 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2022-03-20 00:40:51,103 INFO L87 Difference]: Start difference. First operand 59 states and 71 transitions. Second operand has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 5 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) [2022-03-20 00:40:51,234 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 00:40:51,235 INFO L93 Difference]: Finished difference Result 106 states and 146 transitions. [2022-03-20 00:40:51,235 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-03-20 00:40:51,235 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 5 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) Word has length 69 [2022-03-20 00:40:51,236 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 00:40:51,237 INFO L225 Difference]: With dead ends: 106 [2022-03-20 00:40:51,237 INFO L226 Difference]: Without dead ends: 98 [2022-03-20 00:40:51,237 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 142 GetRequests, 129 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2022-03-20 00:40:51,238 INFO L913 BasicCegarLoop]: 60 mSDtfsCounter, 30 mSDsluCounter, 273 mSDsCounter, 0 mSdLazyCounter, 100 mSolverCounterSat, 53 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 333 SdHoareTripleChecker+Invalid, 153 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 53 IncrementalHoareTripleChecker+Valid, 100 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 00:40:51,238 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [35 Valid, 333 Invalid, 153 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [53 Valid, 100 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 00:40:51,239 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2022-03-20 00:40:51,258 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 89. [2022-03-20 00:40:51,259 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 89 states, 47 states have (on average 1.1914893617021276) internal successors, (56), 48 states have internal predecessors, (56), 34 states have call successors, (34), 8 states have call predecessors, (34), 7 states have return successors, (32), 32 states have call predecessors, (32), 32 states have call successors, (32) [2022-03-20 00:40:51,260 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 122 transitions. [2022-03-20 00:40:51,261 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 122 transitions. Word has length 69 [2022-03-20 00:40:51,262 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 00:40:51,262 INFO L478 AbstractCegarLoop]: Abstraction has 89 states and 122 transitions. [2022-03-20 00:40:51,262 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 5 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) [2022-03-20 00:40:51,262 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 122 transitions. [2022-03-20 00:40:51,264 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2022-03-20 00:40:51,264 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 00:40:51,264 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 6, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 00:40:51,285 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-03-20 00:40:51,479 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 00:40:51,480 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 00:40:51,480 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 00:40:51,480 INFO L85 PathProgramCache]: Analyzing trace with hash 376741854, now seen corresponding path program 1 times [2022-03-20 00:40:51,480 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 00:40:51,480 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [188337038] [2022-03-20 00:40:51,480 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 00:40:51,480 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 00:40:51,494 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 00:40:51,494 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [488482002] [2022-03-20 00:40:51,494 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 00:40:51,494 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 00:40:51,495 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 00:40:51,497 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 00:40:51,499 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-03-20 00:40:51,540 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 00:40:51,541 INFO L263 TraceCheckSpWp]: Trace formula consists of 204 conjuncts, 18 conjunts are in the unsatisfiable core [2022-03-20 00:40:51,545 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 00:40:51,676 INFO L134 CoverageAnalysis]: Checked inductivity of 115 backedges. 15 proven. 12 refuted. 0 times theorem prover too weak. 88 trivial. 0 not checked. [2022-03-20 00:40:51,677 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 00:40:51,808 INFO L134 CoverageAnalysis]: Checked inductivity of 115 backedges. 20 proven. 7 refuted. 0 times theorem prover too weak. 88 trivial. 0 not checked. [2022-03-20 00:40:51,808 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 00:40:51,808 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [188337038] [2022-03-20 00:40:51,808 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 00:40:51,808 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [488482002] [2022-03-20 00:40:51,808 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [488482002] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 00:40:51,808 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 00:40:51,809 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 12 [2022-03-20 00:40:51,809 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [610536034] [2022-03-20 00:40:51,809 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 00:40:51,809 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-03-20 00:40:51,809 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 00:40:51,809 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-03-20 00:40:51,809 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=104, Unknown=0, NotChecked=0, Total=132 [2022-03-20 00:40:51,811 INFO L87 Difference]: Start difference. First operand 89 states and 122 transitions. Second operand has 12 states, 12 states have (on average 3.0) internal successors, (36), 11 states have internal predecessors, (36), 6 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (19), 6 states have call predecessors, (19), 6 states have call successors, (19) [2022-03-20 00:40:52,012 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 00:40:52,012 INFO L93 Difference]: Finished difference Result 132 states and 187 transitions. [2022-03-20 00:40:52,012 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-03-20 00:40:52,013 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 3.0) internal successors, (36), 11 states have internal predecessors, (36), 6 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (19), 6 states have call predecessors, (19), 6 states have call successors, (19) Word has length 75 [2022-03-20 00:40:52,014 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 00:40:52,017 INFO L225 Difference]: With dead ends: 132 [2022-03-20 00:40:52,017 INFO L226 Difference]: Without dead ends: 128 [2022-03-20 00:40:52,018 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 157 GetRequests, 141 SyntacticMatches, 1 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 32 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=58, Invalid=214, Unknown=0, NotChecked=0, Total=272 [2022-03-20 00:40:52,018 INFO L913 BasicCegarLoop]: 46 mSDtfsCounter, 26 mSDsluCounter, 351 mSDsCounter, 0 mSdLazyCounter, 315 mSolverCounterSat, 31 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 397 SdHoareTripleChecker+Invalid, 346 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 31 IncrementalHoareTripleChecker+Valid, 315 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 00:40:52,019 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [32 Valid, 397 Invalid, 346 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [31 Valid, 315 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 00:40:52,019 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 128 states. [2022-03-20 00:40:52,042 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 128 to 96. [2022-03-20 00:40:52,042 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 51 states have (on average 1.1764705882352942) internal successors, (60), 53 states have internal predecessors, (60), 36 states have call successors, (36), 9 states have call predecessors, (36), 8 states have return successors, (34), 33 states have call predecessors, (34), 34 states have call successors, (34) [2022-03-20 00:40:52,044 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 130 transitions. [2022-03-20 00:40:52,044 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 130 transitions. Word has length 75 [2022-03-20 00:40:52,045 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 00:40:52,045 INFO L478 AbstractCegarLoop]: Abstraction has 96 states and 130 transitions. [2022-03-20 00:40:52,045 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 3.0) internal successors, (36), 11 states have internal predecessors, (36), 6 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (19), 6 states have call predecessors, (19), 6 states have call successors, (19) [2022-03-20 00:40:52,045 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 130 transitions. [2022-03-20 00:40:52,048 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 81 [2022-03-20 00:40:52,048 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 00:40:52,048 INFO L499 BasicCegarLoop]: trace histogram [7, 6, 6, 6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 00:40:52,091 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2022-03-20 00:40:52,255 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 00:40:52,256 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 00:40:52,256 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 00:40:52,256 INFO L85 PathProgramCache]: Analyzing trace with hash -1245952186, now seen corresponding path program 2 times [2022-03-20 00:40:52,256 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 00:40:52,256 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [930145295] [2022-03-20 00:40:52,256 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 00:40:52,256 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 00:40:52,264 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 00:40:52,264 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1704401193] [2022-03-20 00:40:52,264 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 00:40:52,265 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 00:40:52,265 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 00:40:52,268 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 00:40:52,270 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-03-20 00:40:52,330 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 00:40:52,331 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 00:40:52,332 INFO L263 TraceCheckSpWp]: Trace formula consists of 213 conjuncts, 33 conjunts are in the unsatisfiable core [2022-03-20 00:40:52,334 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 00:40:52,714 INFO L134 CoverageAnalysis]: Checked inductivity of 138 backedges. 15 proven. 18 refuted. 0 times theorem prover too weak. 105 trivial. 0 not checked. [2022-03-20 00:40:52,714 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 00:40:52,871 INFO L134 CoverageAnalysis]: Checked inductivity of 138 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2022-03-20 00:40:52,871 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 00:40:52,871 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [930145295] [2022-03-20 00:40:52,871 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 00:40:52,872 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1704401193] [2022-03-20 00:40:52,872 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1704401193] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 00:40:52,872 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 00:40:52,872 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 7] total 13 [2022-03-20 00:40:52,872 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1929590053] [2022-03-20 00:40:52,872 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 00:40:52,872 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-03-20 00:40:52,872 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 00:40:52,873 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-03-20 00:40:52,873 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=126, Unknown=0, NotChecked=0, Total=156 [2022-03-20 00:40:52,873 INFO L87 Difference]: Start difference. First operand 96 states and 130 transitions. Second operand has 13 states, 13 states have (on average 2.6153846153846154) internal successors, (34), 11 states have internal predecessors, (34), 8 states have call successors, (26), 2 states have call predecessors, (26), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2022-03-20 00:40:54,201 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 00:40:54,201 INFO L93 Difference]: Finished difference Result 128 states and 169 transitions. [2022-03-20 00:40:54,202 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-03-20 00:40:54,202 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.6153846153846154) internal successors, (34), 11 states have internal predecessors, (34), 8 states have call successors, (26), 2 states have call predecessors, (26), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) Word has length 80 [2022-03-20 00:40:54,202 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 00:40:54,203 INFO L225 Difference]: With dead ends: 128 [2022-03-20 00:40:54,203 INFO L226 Difference]: Without dead ends: 126 [2022-03-20 00:40:54,203 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 167 GetRequests, 147 SyntacticMatches, 1 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 56 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=88, Invalid=332, Unknown=0, NotChecked=0, Total=420 [2022-03-20 00:40:54,203 INFO L913 BasicCegarLoop]: 39 mSDtfsCounter, 40 mSDsluCounter, 266 mSDsCounter, 0 mSdLazyCounter, 257 mSolverCounterSat, 73 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 40 SdHoareTripleChecker+Valid, 305 SdHoareTripleChecker+Invalid, 330 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 73 IncrementalHoareTripleChecker+Valid, 257 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.1s IncrementalHoareTripleChecker+Time [2022-03-20 00:40:54,204 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [40 Valid, 305 Invalid, 330 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [73 Valid, 257 Invalid, 0 Unknown, 0 Unchecked, 1.1s Time] [2022-03-20 00:40:54,204 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 126 states. [2022-03-20 00:40:54,215 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 126 to 108. [2022-03-20 00:40:54,216 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 108 states, 60 states have (on average 1.15) internal successors, (69), 62 states have internal predecessors, (69), 36 states have call successors, (36), 12 states have call predecessors, (36), 11 states have return successors, (34), 33 states have call predecessors, (34), 34 states have call successors, (34) [2022-03-20 00:40:54,216 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 108 states to 108 states and 139 transitions. [2022-03-20 00:40:54,216 INFO L78 Accepts]: Start accepts. Automaton has 108 states and 139 transitions. Word has length 80 [2022-03-20 00:40:54,217 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 00:40:54,217 INFO L478 AbstractCegarLoop]: Abstraction has 108 states and 139 transitions. [2022-03-20 00:40:54,217 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.6153846153846154) internal successors, (34), 11 states have internal predecessors, (34), 8 states have call successors, (26), 2 states have call predecessors, (26), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2022-03-20 00:40:54,217 INFO L276 IsEmpty]: Start isEmpty. Operand 108 states and 139 transitions. [2022-03-20 00:40:54,217 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 86 [2022-03-20 00:40:54,217 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 00:40:54,218 INFO L499 BasicCegarLoop]: trace histogram [8, 7, 7, 6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 00:40:54,243 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2022-03-20 00:40:54,445 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,SelfDestructingSolverStorable8 [2022-03-20 00:40:54,446 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 00:40:54,446 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 00:40:54,446 INFO L85 PathProgramCache]: Analyzing trace with hash 901388446, now seen corresponding path program 3 times [2022-03-20 00:40:54,446 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 00:40:54,446 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2025288632] [2022-03-20 00:40:54,446 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 00:40:54,446 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 00:40:54,454 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 00:40:54,454 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1100865634] [2022-03-20 00:40:54,454 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-03-20 00:40:54,454 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 00:40:54,454 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 00:40:54,461 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 00:40:54,462 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2022-03-20 00:40:54,502 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2022-03-20 00:40:54,503 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 00:40:54,504 INFO L263 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 36 conjunts are in the unsatisfiable core [2022-03-20 00:40:54,505 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 00:40:54,847 INFO L134 CoverageAnalysis]: Checked inductivity of 165 backedges. 31 proven. 8 refuted. 0 times theorem prover too weak. 126 trivial. 0 not checked. [2022-03-20 00:40:54,847 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 00:40:54,917 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 00:40:54,917 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2025288632] [2022-03-20 00:40:54,917 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 00:40:54,917 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1100865634] [2022-03-20 00:40:54,917 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1100865634] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 00:40:54,917 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 00:40:54,917 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2022-03-20 00:40:54,918 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1141209472] [2022-03-20 00:40:54,918 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-20 00:40:54,919 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-03-20 00:40:54,919 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 00:40:54,919 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-03-20 00:40:54,919 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2022-03-20 00:40:54,920 INFO L87 Difference]: Start difference. First operand 108 states and 139 transitions. Second operand has 9 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 8 states have internal predecessors, (25), 4 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2022-03-20 00:40:55,180 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 00:40:55,180 INFO L93 Difference]: Finished difference Result 144 states and 181 transitions. [2022-03-20 00:40:55,181 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-03-20 00:40:55,181 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 8 states have internal predecessors, (25), 4 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) Word has length 85 [2022-03-20 00:40:55,181 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 00:40:55,182 INFO L225 Difference]: With dead ends: 144 [2022-03-20 00:40:55,182 INFO L226 Difference]: Without dead ends: 142 [2022-03-20 00:40:55,182 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 79 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=38, Invalid=144, Unknown=0, NotChecked=0, Total=182 [2022-03-20 00:40:55,183 INFO L913 BasicCegarLoop]: 39 mSDtfsCounter, 20 mSDsluCounter, 194 mSDsCounter, 0 mSdLazyCounter, 191 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 233 SdHoareTripleChecker+Invalid, 205 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 191 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-20 00:40:55,183 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [25 Valid, 233 Invalid, 205 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 191 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-20 00:40:55,184 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 142 states. [2022-03-20 00:40:55,199 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 142 to 139. [2022-03-20 00:40:55,200 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 139 states, 79 states have (on average 1.139240506329114) internal successors, (90), 81 states have internal predecessors, (90), 44 states have call successors, (44), 16 states have call predecessors, (44), 15 states have return successors, (42), 41 states have call predecessors, (42), 42 states have call successors, (42) [2022-03-20 00:40:55,201 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 139 states to 139 states and 176 transitions. [2022-03-20 00:40:55,201 INFO L78 Accepts]: Start accepts. Automaton has 139 states and 176 transitions. Word has length 85 [2022-03-20 00:40:55,201 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 00:40:55,201 INFO L478 AbstractCegarLoop]: Abstraction has 139 states and 176 transitions. [2022-03-20 00:40:55,201 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 8 states have internal predecessors, (25), 4 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2022-03-20 00:40:55,201 INFO L276 IsEmpty]: Start isEmpty. Operand 139 states and 176 transitions. [2022-03-20 00:40:55,202 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2022-03-20 00:40:55,202 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 00:40:55,202 INFO L499 BasicCegarLoop]: trace histogram [9, 8, 8, 6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 00:40:55,221 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2022-03-20 00:40:55,415 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2022-03-20 00:40:55,415 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 00:40:55,415 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 00:40:55,415 INFO L85 PathProgramCache]: Analyzing trace with hash -686534738, now seen corresponding path program 1 times [2022-03-20 00:40:55,415 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 00:40:55,416 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1418019900] [2022-03-20 00:40:55,416 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 00:40:55,416 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 00:40:55,423 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 00:40:55,423 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [992214103] [2022-03-20 00:40:55,423 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 00:40:55,423 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 00:40:55,424 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 00:40:55,425 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 00:40:55,426 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2022-03-20 00:40:55,469 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 00:40:55,471 INFO L263 TraceCheckSpWp]: Trace formula consists of 233 conjuncts, 37 conjunts are in the unsatisfiable core [2022-03-20 00:40:55,473 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 00:40:55,887 INFO L134 CoverageAnalysis]: Checked inductivity of 196 backedges. 16 proven. 8 refuted. 0 times theorem prover too weak. 172 trivial. 0 not checked. [2022-03-20 00:40:55,887 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 00:40:56,207 INFO L134 CoverageAnalysis]: Checked inductivity of 196 backedges. 16 proven. 8 refuted. 0 times theorem prover too weak. 172 trivial. 0 not checked. [2022-03-20 00:40:56,207 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 00:40:56,207 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1418019900] [2022-03-20 00:40:56,207 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 00:40:56,207 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [992214103] [2022-03-20 00:40:56,207 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [992214103] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 00:40:56,207 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 00:40:56,208 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 14 [2022-03-20 00:40:56,208 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [889132363] [2022-03-20 00:40:56,208 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 00:40:56,208 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-03-20 00:40:56,208 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 00:40:56,208 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-03-20 00:40:56,208 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=147, Unknown=0, NotChecked=0, Total=182 [2022-03-20 00:40:56,209 INFO L87 Difference]: Start difference. First operand 139 states and 176 transitions. Second operand has 14 states, 12 states have (on average 2.75) internal successors, (33), 13 states have internal predecessors, (33), 9 states have call successors, (28), 2 states have call predecessors, (28), 1 states have return successors, (25), 7 states have call predecessors, (25), 7 states have call successors, (25) [2022-03-20 00:40:57,698 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 00:40:57,698 INFO L93 Difference]: Finished difference Result 228 states and 311 transitions. [2022-03-20 00:40:57,699 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2022-03-20 00:40:57,699 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 12 states have (on average 2.75) internal successors, (33), 13 states have internal predecessors, (33), 9 states have call successors, (28), 2 states have call predecessors, (28), 1 states have return successors, (25), 7 states have call predecessors, (25), 7 states have call successors, (25) Word has length 91 [2022-03-20 00:40:57,699 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 00:40:57,700 INFO L225 Difference]: With dead ends: 228 [2022-03-20 00:40:57,700 INFO L226 Difference]: Without dead ends: 220 [2022-03-20 00:40:57,701 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 197 GetRequests, 168 SyntacticMatches, 1 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 102 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=178, Invalid=692, Unknown=0, NotChecked=0, Total=870 [2022-03-20 00:40:57,701 INFO L913 BasicCegarLoop]: 78 mSDtfsCounter, 53 mSDsluCounter, 362 mSDsCounter, 0 mSdLazyCounter, 435 mSolverCounterSat, 133 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 57 SdHoareTripleChecker+Valid, 440 SdHoareTripleChecker+Invalid, 568 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 133 IncrementalHoareTripleChecker+Valid, 435 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.1s IncrementalHoareTripleChecker+Time [2022-03-20 00:40:57,701 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [57 Valid, 440 Invalid, 568 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [133 Valid, 435 Invalid, 0 Unknown, 0 Unchecked, 1.1s Time] [2022-03-20 00:40:57,702 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 220 states. [2022-03-20 00:40:57,735 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 220 to 216. [2022-03-20 00:40:57,736 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 216 states, 116 states have (on average 1.1810344827586208) internal successors, (137), 117 states have internal predecessors, (137), 81 states have call successors, (81), 19 states have call predecessors, (81), 18 states have return successors, (79), 79 states have call predecessors, (79), 79 states have call successors, (79) [2022-03-20 00:40:57,737 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 216 states to 216 states and 297 transitions. [2022-03-20 00:40:57,737 INFO L78 Accepts]: Start accepts. Automaton has 216 states and 297 transitions. Word has length 91 [2022-03-20 00:40:57,737 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 00:40:57,737 INFO L478 AbstractCegarLoop]: Abstraction has 216 states and 297 transitions. [2022-03-20 00:40:57,737 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 12 states have (on average 2.75) internal successors, (33), 13 states have internal predecessors, (33), 9 states have call successors, (28), 2 states have call predecessors, (28), 1 states have return successors, (25), 7 states have call predecessors, (25), 7 states have call successors, (25) [2022-03-20 00:40:57,738 INFO L276 IsEmpty]: Start isEmpty. Operand 216 states and 297 transitions. [2022-03-20 00:40:57,739 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2022-03-20 00:40:57,739 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 00:40:57,739 INFO L499 BasicCegarLoop]: trace histogram [12, 11, 11, 6, 6, 6, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 00:40:57,768 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2022-03-20 00:40:57,957 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2022-03-20 00:40:57,958 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 00:40:57,958 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 00:40:57,958 INFO L85 PathProgramCache]: Analyzing trace with hash -428114403, now seen corresponding path program 1 times [2022-03-20 00:40:57,958 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 00:40:57,958 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1358409876] [2022-03-20 00:40:57,958 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 00:40:57,958 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 00:40:57,965 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 00:40:57,965 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1343285979] [2022-03-20 00:40:57,965 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 00:40:57,966 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 00:40:57,966 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 00:40:57,967 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 00:40:57,969 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2022-03-20 00:40:58,031 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 00:40:58,033 INFO L263 TraceCheckSpWp]: Trace formula consists of 264 conjuncts, 54 conjunts are in the unsatisfiable core [2022-03-20 00:40:58,035 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 00:40:58,698 INFO L134 CoverageAnalysis]: Checked inductivity of 320 backedges. 79 proven. 33 refuted. 0 times theorem prover too weak. 208 trivial. 0 not checked. [2022-03-20 00:40:58,699 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 00:41:10,347 INFO L134 CoverageAnalysis]: Checked inductivity of 320 backedges. 79 proven. 27 refuted. 6 times theorem prover too weak. 208 trivial. 0 not checked. [2022-03-20 00:41:10,348 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 00:41:10,348 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1358409876] [2022-03-20 00:41:10,348 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 00:41:10,348 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1343285979] [2022-03-20 00:41:10,348 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1343285979] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 00:41:10,348 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 00:41:10,348 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 13] total 19 [2022-03-20 00:41:10,348 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [234892060] [2022-03-20 00:41:10,348 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 00:41:10,348 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2022-03-20 00:41:10,349 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 00:41:10,349 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2022-03-20 00:41:10,349 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=260, Unknown=4, NotChecked=0, Total=342 [2022-03-20 00:41:10,349 INFO L87 Difference]: Start difference. First operand 216 states and 297 transitions. Second operand has 19 states, 17 states have (on average 2.3529411764705883) internal successors, (40), 16 states have internal predecessors, (40), 11 states have call successors, (34), 2 states have call predecessors, (34), 2 states have return successors, (31), 13 states have call predecessors, (31), 10 states have call successors, (31) [2022-03-20 00:41:12,246 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.88s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:41:40,215 WARN L232 SmtUtils]: Spent 25.22s on a formula simplification. DAG size of input: 85 DAG size of output: 84 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 00:41:42,231 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:41:46,594 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-03-20 00:41:48,719 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:41:50,744 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:41:52,766 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-03-20 00:41:54,776 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-03-20 00:41:58,891 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:42:01,217 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:42:03,450 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:42:04,824 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.09s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:42:44,175 WARN L232 SmtUtils]: Spent 35.05s on a formula simplification. DAG size of input: 63 DAG size of output: 62 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 00:42:46,209 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:42:48,371 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:42:50,447 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:42:52,507 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:42:55,376 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-03-20 00:43:12,849 WARN L232 SmtUtils]: Spent 16.37s on a formula simplification. DAG size of input: 63 DAG size of output: 62 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 00:43:15,515 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:43:38,189 WARN L232 SmtUtils]: Spent 20.35s on a formula simplification that was a NOOP. DAG size: 85 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 00:43:40,300 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.91s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:43:42,738 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:43:44,746 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-03-20 00:43:45,778 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.03s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:44:27,553 WARN L232 SmtUtils]: Spent 39.47s on a formula simplification. DAG size of input: 86 DAG size of output: 85 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 00:44:28,960 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.30s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:44:30,775 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.37s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:44:32,859 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:44:52,429 WARN L232 SmtUtils]: Spent 19.11s on a formula simplification that was a NOOP. DAG size: 85 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 00:44:54,790 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:44:56,792 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:45:05,845 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-03-20 00:45:07,875 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-03-20 00:45:25,439 WARN L232 SmtUtils]: Spent 15.57s on a formula simplification. DAG size of input: 86 DAG size of output: 64 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 00:45:59,056 WARN L232 SmtUtils]: Spent 30.74s on a formula simplification. DAG size of input: 85 DAG size of output: 67 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 00:46:01,061 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:46:03,362 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-03-20 00:46:04,345 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 00:46:04,346 INFO L93 Difference]: Finished difference Result 278 states and 384 transitions. [2022-03-20 00:46:04,346 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2022-03-20 00:46:04,346 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 17 states have (on average 2.3529411764705883) internal successors, (40), 16 states have internal predecessors, (40), 11 states have call successors, (34), 2 states have call predecessors, (34), 2 states have return successors, (31), 13 states have call predecessors, (31), 10 states have call successors, (31) Word has length 107 [2022-03-20 00:46:04,346 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 00:46:04,348 INFO L225 Difference]: With dead ends: 278 [2022-03-20 00:46:04,348 INFO L226 Difference]: Without dead ends: 276 [2022-03-20 00:46:04,349 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 232 GetRequests, 196 SyntacticMatches, 3 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 188 ImplicationChecksByTransitivity, 240.3s TimeCoverageRelationStatistics Valid=300, Invalid=875, Unknown=15, NotChecked=0, Total=1190 [2022-03-20 00:46:04,349 INFO L913 BasicCegarLoop]: 44 mSDtfsCounter, 75 mSDsluCounter, 420 mSDsCounter, 0 mSdLazyCounter, 630 mSolverCounterSat, 134 mSolverCounterUnsat, 24 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 62.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 83 SdHoareTripleChecker+Valid, 464 SdHoareTripleChecker+Invalid, 788 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 134 IncrementalHoareTripleChecker+Valid, 630 IncrementalHoareTripleChecker+Invalid, 24 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 63.0s IncrementalHoareTripleChecker+Time [2022-03-20 00:46:04,349 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [83 Valid, 464 Invalid, 788 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [134 Valid, 630 Invalid, 24 Unknown, 0 Unchecked, 63.0s Time] [2022-03-20 00:46:04,350 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 276 states. [2022-03-20 00:46:04,427 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 276 to 260. [2022-03-20 00:46:04,428 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 260 states, 139 states have (on average 1.1798561151079137) internal successors, (164), 142 states have internal predecessors, (164), 101 states have call successors, (101), 20 states have call predecessors, (101), 19 states have return successors, (99), 97 states have call predecessors, (99), 99 states have call successors, (99) [2022-03-20 00:46:04,429 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 260 states to 260 states and 364 transitions. [2022-03-20 00:46:04,429 INFO L78 Accepts]: Start accepts. Automaton has 260 states and 364 transitions. Word has length 107 [2022-03-20 00:46:04,430 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 00:46:04,430 INFO L478 AbstractCegarLoop]: Abstraction has 260 states and 364 transitions. [2022-03-20 00:46:04,430 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 17 states have (on average 2.3529411764705883) internal successors, (40), 16 states have internal predecessors, (40), 11 states have call successors, (34), 2 states have call predecessors, (34), 2 states have return successors, (31), 13 states have call predecessors, (31), 10 states have call successors, (31) [2022-03-20 00:46:04,430 INFO L276 IsEmpty]: Start isEmpty. Operand 260 states and 364 transitions. [2022-03-20 00:46:04,431 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 111 [2022-03-20 00:46:04,431 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 00:46:04,431 INFO L499 BasicCegarLoop]: trace histogram [12, 11, 11, 6, 6, 6, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 00:46:04,450 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2022-03-20 00:46:04,632 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2022-03-20 00:46:04,632 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 00:46:04,632 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 00:46:04,632 INFO L85 PathProgramCache]: Analyzing trace with hash -1979573154, now seen corresponding path program 4 times [2022-03-20 00:46:04,632 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 00:46:04,632 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1810808307] [2022-03-20 00:46:04,632 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 00:46:04,633 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 00:46:04,639 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 00:46:04,639 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1403808507] [2022-03-20 00:46:04,639 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-20 00:46:04,639 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 00:46:04,639 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 00:46:04,641 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 00:46:04,642 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2022-03-20 00:46:04,686 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-20 00:46:04,687 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 00:46:04,687 INFO L263 TraceCheckSpWp]: Trace formula consists of 233 conjuncts, 5 conjunts are in the unsatisfiable core [2022-03-20 00:46:04,689 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 00:46:04,825 INFO L134 CoverageAnalysis]: Checked inductivity of 325 backedges. 135 proven. 0 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2022-03-20 00:46:04,825 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 00:46:04,825 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 00:46:04,826 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1810808307] [2022-03-20 00:46:04,826 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 00:46:04,826 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1403808507] [2022-03-20 00:46:04,826 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1403808507] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 00:46:04,826 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 00:46:04,826 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 00:46:04,826 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [615269825] [2022-03-20 00:46:04,826 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 00:46:04,826 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 00:46:04,826 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 00:46:04,827 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 00:46:04,827 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-20 00:46:04,827 INFO L87 Difference]: Start difference. First operand 260 states and 364 transitions. Second operand has 5 states, 5 states have (on average 5.8) internal successors, (29), 5 states have internal predecessors, (29), 3 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 3 states have call predecessors, (18), 3 states have call successors, (18) [2022-03-20 00:46:04,899 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 00:46:04,899 INFO L93 Difference]: Finished difference Result 325 states and 445 transitions. [2022-03-20 00:46:04,899 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-03-20 00:46:04,899 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.8) internal successors, (29), 5 states have internal predecessors, (29), 3 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 3 states have call predecessors, (18), 3 states have call successors, (18) Word has length 110 [2022-03-20 00:46:04,900 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 00:46:04,900 INFO L225 Difference]: With dead ends: 325 [2022-03-20 00:46:04,900 INFO L226 Difference]: Without dead ends: 199 [2022-03-20 00:46:04,902 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 111 GetRequests, 106 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2022-03-20 00:46:04,903 INFO L913 BasicCegarLoop]: 56 mSDtfsCounter, 6 mSDsluCounter, 127 mSDsCounter, 0 mSdLazyCounter, 42 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 183 SdHoareTripleChecker+Invalid, 47 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 42 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 00:46:04,903 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 183 Invalid, 47 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 42 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 00:46:04,903 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 199 states. [2022-03-20 00:46:04,926 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 199 to 123. [2022-03-20 00:46:04,926 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 123 states, 68 states have (on average 1.1176470588235294) internal successors, (76), 68 states have internal predecessors, (76), 41 states have call successors, (41), 15 states have call predecessors, (41), 13 states have return successors, (39), 39 states have call predecessors, (39), 39 states have call successors, (39) [2022-03-20 00:46:04,926 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 123 states to 123 states and 156 transitions. [2022-03-20 00:46:04,927 INFO L78 Accepts]: Start accepts. Automaton has 123 states and 156 transitions. Word has length 110 [2022-03-20 00:46:04,928 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 00:46:04,928 INFO L478 AbstractCegarLoop]: Abstraction has 123 states and 156 transitions. [2022-03-20 00:46:04,928 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.8) internal successors, (29), 5 states have internal predecessors, (29), 3 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 3 states have call predecessors, (18), 3 states have call successors, (18) [2022-03-20 00:46:04,928 INFO L276 IsEmpty]: Start isEmpty. Operand 123 states and 156 transitions. [2022-03-20 00:46:04,929 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 139 [2022-03-20 00:46:04,929 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 00:46:04,929 INFO L499 BasicCegarLoop]: trace histogram [17, 16, 16, 6, 6, 6, 4, 4, 4, 4, 4, 4, 4, 4, 4, 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, 1] [2022-03-20 00:46:04,945 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2022-03-20 00:46:05,142 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2022-03-20 00:46:05,143 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 00:46:05,143 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 00:46:05,143 INFO L85 PathProgramCache]: Analyzing trace with hash -896647763, now seen corresponding path program 2 times [2022-03-20 00:46:05,143 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 00:46:05,143 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1276313737] [2022-03-20 00:46:05,143 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 00:46:05,143 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 00:46:05,150 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 00:46:05,150 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [891951872] [2022-03-20 00:46:05,150 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 00:46:05,150 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 00:46:05,150 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 00:46:05,151 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 00:46:05,152 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2022-03-20 00:46:05,208 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 00:46:05,208 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 00:46:05,210 INFO L263 TraceCheckSpWp]: Trace formula consists of 333 conjuncts, 67 conjunts are in the unsatisfiable core [2022-03-20 00:46:05,212 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 00:46:06,919 INFO L134 CoverageAnalysis]: Checked inductivity of 615 backedges. 69 proven. 90 refuted. 0 times theorem prover too weak. 456 trivial. 0 not checked. [2022-03-20 00:46:06,919 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 00:46:07,614 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-20 00:46:07,617 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-20 00:46:19,256 INFO L134 CoverageAnalysis]: Checked inductivity of 615 backedges. 69 proven. 90 refuted. 0 times theorem prover too weak. 456 trivial. 0 not checked. [2022-03-20 00:46:19,256 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 00:46:19,256 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1276313737] [2022-03-20 00:46:19,256 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 00:46:19,256 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [891951872] [2022-03-20 00:46:19,256 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [891951872] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 00:46:19,256 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 00:46:19,256 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17] total 29 [2022-03-20 00:46:19,256 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1607924870] [2022-03-20 00:46:19,256 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 00:46:19,257 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2022-03-20 00:46:19,257 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 00:46:19,257 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2022-03-20 00:46:19,257 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=135, Invalid=674, Unknown=3, NotChecked=0, Total=812 [2022-03-20 00:46:19,258 INFO L87 Difference]: Start difference. First operand 123 states and 156 transitions. Second operand has 29 states, 27 states have (on average 1.9259259259259258) internal successors, (52), 26 states have internal predecessors, (52), 16 states have call successors, (44), 2 states have call predecessors, (44), 2 states have return successors, (41), 12 states have call predecessors, (41), 14 states have call successors, (41) [2022-03-20 00:46:29,869 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:46:34,145 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:46:36,147 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:46:38,150 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:46:40,337 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:46:48,715 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:46:50,965 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:46:55,285 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:46:57,456 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:47:12,546 WARN L232 SmtUtils]: Spent 13.94s on a formula simplification. DAG size of input: 117 DAG size of output: 115 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 00:47:25,219 WARN L232 SmtUtils]: Spent 9.89s on a formula simplification. DAG size of input: 103 DAG size of output: 101 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 00:47:27,728 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:47:30,206 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:47:32,209 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:47:33,991 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.78s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:47:36,796 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:48:01,059 WARN L232 SmtUtils]: Spent 14.90s on a formula simplification that was a NOOP. DAG size: 74 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 00:48:41,847 WARN L232 SmtUtils]: Spent 39.68s on a formula simplification. DAG size of input: 121 DAG size of output: 119 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 00:48:44,576 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:49:15,885 WARN L232 SmtUtils]: Spent 26.17s on a formula simplification. DAG size of input: 100 DAG size of output: 98 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 00:49:26,309 WARN L232 SmtUtils]: Spent 6.50s on a formula simplification. DAG size of input: 96 DAG size of output: 94 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 00:49:45,008 WARN L232 SmtUtils]: Spent 9.61s on a formula simplification. DAG size of input: 102 DAG size of output: 100 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 00:49:54,679 WARN L232 SmtUtils]: Spent 7.38s on a formula simplification. DAG size of input: 101 DAG size of output: 99 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 00:49:59,791 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:50:01,338 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 00:50:01,338 INFO L93 Difference]: Finished difference Result 246 states and 335 transitions. [2022-03-20 00:50:01,339 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 47 states. [2022-03-20 00:50:01,339 INFO L78 Accepts]: Start accepts. Automaton has has 29 states, 27 states have (on average 1.9259259259259258) internal successors, (52), 26 states have internal predecessors, (52), 16 states have call successors, (44), 2 states have call predecessors, (44), 2 states have return successors, (41), 12 states have call predecessors, (41), 14 states have call successors, (41) Word has length 138 [2022-03-20 00:50:01,339 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 00:50:01,340 INFO L225 Difference]: With dead ends: 246 [2022-03-20 00:50:01,340 INFO L226 Difference]: Without dead ends: 240 [2022-03-20 00:50:01,341 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 313 GetRequests, 246 SyntacticMatches, 2 SemanticMatches, 65 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1176 ImplicationChecksByTransitivity, 184.4s TimeCoverageRelationStatistics Valid=886, Invalid=3526, Unknown=10, NotChecked=0, Total=4422 [2022-03-20 00:50:01,341 INFO L913 BasicCegarLoop]: 60 mSDtfsCounter, 160 mSDsluCounter, 567 mSDsCounter, 0 mSdLazyCounter, 1129 mSolverCounterSat, 423 mSolverCounterUnsat, 15 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 48.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 165 SdHoareTripleChecker+Valid, 627 SdHoareTripleChecker+Invalid, 1567 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 423 IncrementalHoareTripleChecker+Valid, 1129 IncrementalHoareTripleChecker+Invalid, 15 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 48.6s IncrementalHoareTripleChecker+Time [2022-03-20 00:50:01,342 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [165 Valid, 627 Invalid, 1567 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [423 Valid, 1129 Invalid, 15 Unknown, 0 Unchecked, 48.6s Time] [2022-03-20 00:50:01,342 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 240 states. [2022-03-20 00:50:01,398 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 240 to 174. [2022-03-20 00:50:01,398 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 174 states, 96 states have (on average 1.1041666666666667) internal successors, (106), 96 states have internal predecessors, (106), 61 states have call successors, (61), 18 states have call predecessors, (61), 16 states have return successors, (59), 59 states have call predecessors, (59), 59 states have call successors, (59) [2022-03-20 00:50:01,411 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 174 states to 174 states and 226 transitions. [2022-03-20 00:50:01,411 INFO L78 Accepts]: Start accepts. Automaton has 174 states and 226 transitions. Word has length 138 [2022-03-20 00:50:01,413 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 00:50:01,413 INFO L478 AbstractCegarLoop]: Abstraction has 174 states and 226 transitions. [2022-03-20 00:50:01,413 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 29 states, 27 states have (on average 1.9259259259259258) internal successors, (52), 26 states have internal predecessors, (52), 16 states have call successors, (44), 2 states have call predecessors, (44), 2 states have return successors, (41), 12 states have call predecessors, (41), 14 states have call successors, (41) [2022-03-20 00:50:01,413 INFO L276 IsEmpty]: Start isEmpty. Operand 174 states and 226 transitions. [2022-03-20 00:50:01,414 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 183 [2022-03-20 00:50:01,414 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 00:50:01,414 INFO L499 BasicCegarLoop]: trace histogram [25, 24, 24, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 00:50:01,440 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2022-03-20 00:50:01,631 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2022-03-20 00:50:01,631 INFO L403 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 00:50:01,631 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 00:50:01,631 INFO L85 PathProgramCache]: Analyzing trace with hash -1363924019, now seen corresponding path program 3 times [2022-03-20 00:50:01,632 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 00:50:01,632 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [781782109] [2022-03-20 00:50:01,632 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 00:50:01,632 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 00:50:01,639 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 00:50:01,639 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1366528690] [2022-03-20 00:50:01,639 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-03-20 00:50:01,639 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 00:50:01,639 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 00:50:01,642 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 00:50:01,643 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2022-03-20 00:50:02,113 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2022-03-20 00:50:02,113 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 00:50:02,115 INFO L263 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 70 conjunts are in the unsatisfiable core [2022-03-20 00:50:02,118 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 00:50:03,555 INFO L134 CoverageAnalysis]: Checked inductivity of 1309 backedges. 175 proven. 99 refuted. 0 times theorem prover too weak. 1035 trivial. 0 not checked. [2022-03-20 00:50:03,555 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 00:50:05,038 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-20 00:50:37,578 INFO L134 CoverageAnalysis]: Checked inductivity of 1309 backedges. 169 proven. 90 refuted. 0 times theorem prover too weak. 1050 trivial. 0 not checked. [2022-03-20 00:50:37,578 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 00:50:37,579 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [781782109] [2022-03-20 00:50:37,579 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 00:50:37,579 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1366528690] [2022-03-20 00:50:37,579 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1366528690] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 00:50:37,579 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 00:50:37,579 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 17] total 31 [2022-03-20 00:50:37,579 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [631962486] [2022-03-20 00:50:37,579 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 00:50:37,579 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 31 states [2022-03-20 00:50:37,579 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 00:50:37,580 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2022-03-20 00:50:37,580 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=157, Invalid=769, Unknown=4, NotChecked=0, Total=930 [2022-03-20 00:50:37,580 INFO L87 Difference]: Start difference. First operand 174 states and 226 transitions. Second operand has 31 states, 28 states have (on average 2.0714285714285716) internal successors, (58), 27 states have internal predecessors, (58), 17 states have call successors, (47), 2 states have call predecessors, (47), 3 states have return successors, (45), 13 states have call predecessors, (45), 15 states have call successors, (45) [2022-03-20 00:50:41,863 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:51:13,825 WARN L232 SmtUtils]: Spent 30.99s on a formula simplification that was a NOOP. DAG size: 151 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 00:51:25,174 WARN L232 SmtUtils]: Spent 6.79s on a formula simplification that was a NOOP. DAG size: 137 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 00:51:27,180 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:51:31,179 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:51:43,512 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:51:45,514 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:52:19,356 WARN L232 SmtUtils]: Spent 30.32s on a formula simplification that was a NOOP. DAG size: 115 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 00:52:21,670 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:52:23,672 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:52:25,680 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:52:27,683 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:52:30,372 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:52:32,374 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:52:52,146 WARN L232 SmtUtils]: Spent 13.02s on a formula simplification that was a NOOP. DAG size: 111 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 00:52:55,275 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:52:57,314 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:53:14,423 WARN L232 SmtUtils]: Spent 9.49s on a formula simplification that was a NOOP. DAG size: 111 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 00:53:16,504 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:53:44,940 WARN L232 SmtUtils]: Spent 27.65s on a formula simplification that was a NOOP. DAG size: 150 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 00:53:46,943 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:54:10,893 WARN L232 SmtUtils]: Spent 19.08s on a formula simplification that was a NOOP. DAG size: 101 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 00:54:12,900 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:54:38,380 WARN L232 SmtUtils]: Spent 20.54s on a formula simplification that was a NOOP. DAG size: 115 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 00:54:48,426 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:54:50,428 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:54:52,431 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:54:54,959 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:54:56,961 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:54:58,964 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:55:11,483 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:55:13,586 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 00:55:15,599 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 []