./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/fermat1-ll_unwindbound100.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 839c364b Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/fermat1-ll_unwindbound100.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness.graphml --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash ac7d6bbeae1af74610eb5ea0ec9cc56676532539c7535ebfdf72e0c17174815d --- Real Ultimate output --- This is Ultimate 0.2.2-839c364b5d67a0f615c82cb70ab247790648d4a9-839c364 [2021-12-14 14:06:24,446 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-12-14 14:06:24,453 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-12-14 14:06:24,495 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-12-14 14:06:24,497 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-12-14 14:06:24,501 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-12-14 14:06:24,503 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-12-14 14:06:24,507 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-12-14 14:06:24,508 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-12-14 14:06:24,514 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-12-14 14:06:24,515 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-12-14 14:06:24,516 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-12-14 14:06:24,516 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-12-14 14:06:24,518 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-12-14 14:06:24,521 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-12-14 14:06:24,522 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-12-14 14:06:24,526 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-12-14 14:06:24,527 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-12-14 14:06:24,529 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-12-14 14:06:24,534 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-12-14 14:06:24,537 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-12-14 14:06:24,539 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-12-14 14:06:24,539 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-12-14 14:06:24,541 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-12-14 14:06:24,544 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-12-14 14:06:24,546 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-12-14 14:06:24,546 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-12-14 14:06:24,547 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-12-14 14:06:24,548 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-12-14 14:06:24,548 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-12-14 14:06:24,549 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-12-14 14:06:24,550 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-12-14 14:06:24,551 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-12-14 14:06:24,552 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-12-14 14:06:24,553 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-12-14 14:06:24,553 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-12-14 14:06:24,554 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-12-14 14:06:24,554 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-12-14 14:06:24,554 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-12-14 14:06:24,555 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-12-14 14:06:24,555 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-12-14 14:06:24,556 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2021-12-14 14:06:24,590 INFO L113 SettingsManager]: Loading preferences was successful [2021-12-14 14:06:24,590 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-12-14 14:06:24,590 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2021-12-14 14:06:24,591 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2021-12-14 14:06:24,591 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2021-12-14 14:06:24,591 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2021-12-14 14:06:24,592 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2021-12-14 14:06:24,592 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2021-12-14 14:06:24,592 INFO L138 SettingsManager]: * Use SBE=true [2021-12-14 14:06:24,592 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-12-14 14:06:24,592 INFO L138 SettingsManager]: * sizeof long=4 [2021-12-14 14:06:24,593 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-12-14 14:06:24,593 INFO L138 SettingsManager]: * sizeof POINTER=4 [2021-12-14 14:06:24,593 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-12-14 14:06:24,593 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2021-12-14 14:06:24,593 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2021-12-14 14:06:24,593 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2021-12-14 14:06:24,594 INFO L138 SettingsManager]: * sizeof long double=12 [2021-12-14 14:06:24,594 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2021-12-14 14:06:24,594 INFO L138 SettingsManager]: * Use constant arrays=true [2021-12-14 14:06:24,594 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2021-12-14 14:06:24,594 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-12-14 14:06:24,594 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2021-12-14 14:06:24,595 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2021-12-14 14:06:24,595 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-12-14 14:06:24,601 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-12-14 14:06:24,601 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2021-12-14 14:06:24,602 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2021-12-14 14:06:24,602 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2021-12-14 14:06:24,602 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2021-12-14 14:06:24,603 INFO L138 SettingsManager]: * Large block encoding in concurrent analysis=OFF [2021-12-14 14:06:24,603 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2021-12-14 14:06:24,603 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2021-12-14 14:06:24,603 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2021-12-14 14:06:24,603 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.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness.graphml Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> ac7d6bbeae1af74610eb5ea0ec9cc56676532539c7535ebfdf72e0c17174815d [2021-12-14 14:06:24,849 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-12-14 14:06:24,876 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-12-14 14:06:24,879 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-12-14 14:06:24,880 INFO L271 PluginConnector]: Initializing CDTParser... [2021-12-14 14:06:24,880 INFO L275 PluginConnector]: CDTParser initialized [2021-12-14 14:06:24,881 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/fermat1-ll_unwindbound100.c [2021-12-14 14:06:24,941 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/e757f10b2/9da276b511c14b43a3b76c80870e7aac/FLAGead9b531f [2021-12-14 14:06:25,285 INFO L306 CDTParser]: Found 1 translation units. [2021-12-14 14:06:25,285 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/fermat1-ll_unwindbound100.c [2021-12-14 14:06:25,291 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/e757f10b2/9da276b511c14b43a3b76c80870e7aac/FLAGead9b531f [2021-12-14 14:06:25,308 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/e757f10b2/9da276b511c14b43a3b76c80870e7aac [2021-12-14 14:06:25,311 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-12-14 14:06:25,312 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2021-12-14 14:06:25,315 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2021-12-14 14:06:25,315 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2021-12-14 14:06:25,318 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2021-12-14 14:06:25,318 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.12 02:06:25" (1/1) ... [2021-12-14 14:06:25,320 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2a04dab7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 02:06:25, skipping insertion in model container [2021-12-14 14:06:25,320 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.12 02:06:25" (1/1) ... [2021-12-14 14:06:25,326 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2021-12-14 14:06:25,344 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-12-14 14:06:25,481 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/fermat1-ll_unwindbound100.c[535,548] [2021-12-14 14:06:25,514 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-14 14:06:25,523 INFO L203 MainTranslator]: Completed pre-run [2021-12-14 14:06:25,539 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/fermat1-ll_unwindbound100.c[535,548] [2021-12-14 14:06:25,562 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-14 14:06:25,584 INFO L208 MainTranslator]: Completed translation [2021-12-14 14:06:25,584 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 02:06:25 WrapperNode [2021-12-14 14:06:25,585 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2021-12-14 14:06:25,586 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2021-12-14 14:06:25,586 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2021-12-14 14:06:25,586 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2021-12-14 14:06:25,592 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 02:06:25" (1/1) ... [2021-12-14 14:06:25,604 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 02:06:25" (1/1) ... [2021-12-14 14:06:25,626 INFO L137 Inliner]: procedures = 14, calls = 13, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 67 [2021-12-14 14:06:25,626 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2021-12-14 14:06:25,627 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2021-12-14 14:06:25,627 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2021-12-14 14:06:25,627 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2021-12-14 14:06:25,635 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 02:06:25" (1/1) ... [2021-12-14 14:06:25,636 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 02:06:25" (1/1) ... [2021-12-14 14:06:25,639 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 02:06:25" (1/1) ... [2021-12-14 14:06:25,640 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 02:06:25" (1/1) ... [2021-12-14 14:06:25,653 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 02:06:25" (1/1) ... [2021-12-14 14:06:25,658 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 02:06:25" (1/1) ... [2021-12-14 14:06:25,663 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 02:06:25" (1/1) ... [2021-12-14 14:06:25,669 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2021-12-14 14:06:25,671 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2021-12-14 14:06:25,672 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2021-12-14 14:06:25,672 INFO L275 PluginConnector]: RCFGBuilder initialized [2021-12-14 14:06:25,673 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 02:06:25" (1/1) ... [2021-12-14 14:06:25,679 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-12-14 14:06:25,690 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 14:06:25,704 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) [2021-12-14 14:06:25,729 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 [2021-12-14 14:06:25,748 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2021-12-14 14:06:25,748 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2021-12-14 14:06:25,748 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2021-12-14 14:06:25,749 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2021-12-14 14:06:25,749 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2021-12-14 14:06:25,749 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2021-12-14 14:06:25,749 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2021-12-14 14:06:25,749 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2021-12-14 14:06:25,803 INFO L236 CfgBuilder]: Building ICFG [2021-12-14 14:06:25,805 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2021-12-14 14:06:25,943 INFO L277 CfgBuilder]: Performing block encoding [2021-12-14 14:06:25,948 INFO L296 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2021-12-14 14:06:25,949 INFO L301 CfgBuilder]: Removed 3 assume(true) statements. [2021-12-14 14:06:25,950 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.12 02:06:25 BoogieIcfgContainer [2021-12-14 14:06:25,951 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2021-12-14 14:06:25,952 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2021-12-14 14:06:25,952 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2021-12-14 14:06:25,955 INFO L275 PluginConnector]: TraceAbstraction initialized [2021-12-14 14:06:25,956 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 14.12 02:06:25" (1/3) ... [2021-12-14 14:06:25,956 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@46cc231f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.12 02:06:25, skipping insertion in model container [2021-12-14 14:06:25,956 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 02:06:25" (2/3) ... [2021-12-14 14:06:25,957 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@46cc231f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.12 02:06:25, skipping insertion in model container [2021-12-14 14:06:25,957 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.12 02:06:25" (3/3) ... [2021-12-14 14:06:25,958 INFO L111 eAbstractionObserver]: Analyzing ICFG fermat1-ll_unwindbound100.c [2021-12-14 14:06:25,963 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2021-12-14 14:06:25,963 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2021-12-14 14:06:26,002 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2021-12-14 14:06:26,007 INFO L339 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, mLoopAccelerationTechnique=FAST_UPR [2021-12-14 14:06:26,008 INFO L340 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2021-12-14 14:06:26,021 INFO L276 IsEmpty]: Start isEmpty. Operand has 32 states, 22 states have (on average 1.5454545454545454) internal successors, (34), 23 states have internal predecessors, (34), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2021-12-14 14:06:26,025 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2021-12-14 14:06:26,025 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 14:06:26,026 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 14:06:26,027 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 14:06:26,031 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 14:06:26,031 INFO L85 PathProgramCache]: Analyzing trace with hash 738208203, now seen corresponding path program 1 times [2021-12-14 14:06:26,039 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 14:06:26,040 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1030855612] [2021-12-14 14:06:26,040 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:06:26,041 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 14:06:26,114 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-14 14:06:26,115 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [806883853] [2021-12-14 14:06:26,123 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:06:26,123 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:06:26,123 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 14:06:26,125 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) [2021-12-14 14:06:26,128 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2021-12-14 14:06:26,210 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:06:26,221 INFO L263 TraceCheckSpWp]: Trace formula consists of 65 conjuncts, 1 conjunts are in the unsatisfiable core [2021-12-14 14:06:26,225 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 14:06:26,315 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2021-12-14 14:06:26,315 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-14 14:06:26,316 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 14:06:26,316 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1030855612] [2021-12-14 14:06:26,316 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-14 14:06:26,317 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [806883853] [2021-12-14 14:06:26,317 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [806883853] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-14 14:06:26,317 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-14 14:06:26,318 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2021-12-14 14:06:26,320 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [633542763] [2021-12-14 14:06:26,320 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-14 14:06:26,324 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2021-12-14 14:06:26,324 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 14:06:26,350 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2021-12-14 14:06:26,351 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2021-12-14 14:06:26,354 INFO L87 Difference]: Start difference. First operand has 32 states, 22 states have (on average 1.5454545454545454) internal successors, (34), 23 states have internal predecessors, (34), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Second operand has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2021-12-14 14:06:26,381 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 14:06:26,381 INFO L93 Difference]: Finished difference Result 61 states and 94 transitions. [2021-12-14 14:06:26,382 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2021-12-14 14:06:26,383 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 18 [2021-12-14 14:06:26,384 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 14:06:26,390 INFO L225 Difference]: With dead ends: 61 [2021-12-14 14:06:26,391 INFO L226 Difference]: Without dead ends: 28 [2021-12-14 14:06:26,395 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2021-12-14 14:06:26,403 INFO L933 BasicCegarLoop]: 41 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 41 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-14 14:06:26,405 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-14 14:06:26,419 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2021-12-14 14:06:26,449 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 28. [2021-12-14 14:06:26,450 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 19 states have (on average 1.368421052631579) internal successors, (26), 20 states have internal predecessors, (26), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2021-12-14 14:06:26,453 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 37 transitions. [2021-12-14 14:06:26,455 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 37 transitions. Word has length 18 [2021-12-14 14:06:26,455 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 14:06:26,455 INFO L470 AbstractCegarLoop]: Abstraction has 28 states and 37 transitions. [2021-12-14 14:06:26,456 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2021-12-14 14:06:26,456 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 37 transitions. [2021-12-14 14:06:26,458 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2021-12-14 14:06:26,458 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 14:06:26,459 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 14:06:26,485 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2021-12-14 14:06:26,682 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2021-12-14 14:06:26,683 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 14:06:26,683 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 14:06:26,683 INFO L85 PathProgramCache]: Analyzing trace with hash -1770759922, now seen corresponding path program 1 times [2021-12-14 14:06:26,684 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 14:06:26,684 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [215769068] [2021-12-14 14:06:26,684 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:06:26,684 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 14:06:26,696 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-14 14:06:26,701 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [394246706] [2021-12-14 14:06:26,701 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:06:26,702 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:06:26,702 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 14:06:26,707 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) [2021-12-14 14:06:26,713 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2021-12-14 14:06:26,752 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:06:26,753 INFO L263 TraceCheckSpWp]: Trace formula consists of 69 conjuncts, 3 conjunts are in the unsatisfiable core [2021-12-14 14:06:26,755 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 14:06:26,848 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-12-14 14:06:26,848 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-14 14:06:26,848 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 14:06:26,849 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [215769068] [2021-12-14 14:06:26,849 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-14 14:06:26,849 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [394246706] [2021-12-14 14:06:26,849 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [394246706] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-14 14:06:26,849 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-14 14:06:26,850 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2021-12-14 14:06:26,850 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [661164033] [2021-12-14 14:06:26,850 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-14 14:06:26,851 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2021-12-14 14:06:26,851 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 14:06:26,852 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-12-14 14:06:26,852 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-12-14 14:06:26,853 INFO L87 Difference]: Start difference. First operand 28 states and 37 transitions. Second operand has 4 states, 4 states have (on average 2.75) internal successors, (11), 3 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2021-12-14 14:06:26,871 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 14:06:26,872 INFO L93 Difference]: Finished difference Result 37 states and 46 transitions. [2021-12-14 14:06:26,872 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2021-12-14 14:06:26,872 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 3 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 19 [2021-12-14 14:06:26,873 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 14:06:26,873 INFO L225 Difference]: With dead ends: 37 [2021-12-14 14:06:26,873 INFO L226 Difference]: Without dead ends: 30 [2021-12-14 14:06:26,874 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 16 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-12-14 14:06:26,875 INFO L933 BasicCegarLoop]: 35 mSDtfsCounter, 0 mSDsluCounter, 56 mSDsCounter, 0 mSdLazyCounter, 10 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 91 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 10 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-14 14:06:26,875 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 91 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 10 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-14 14:06:26,876 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2021-12-14 14:06:26,880 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 30. [2021-12-14 14:06:26,880 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 21 states have (on average 1.3333333333333333) internal successors, (28), 22 states have internal predecessors, (28), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2021-12-14 14:06:26,881 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 39 transitions. [2021-12-14 14:06:26,881 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 39 transitions. Word has length 19 [2021-12-14 14:06:26,882 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 14:06:26,883 INFO L470 AbstractCegarLoop]: Abstraction has 30 states and 39 transitions. [2021-12-14 14:06:26,883 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 3 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2021-12-14 14:06:26,883 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 39 transitions. [2021-12-14 14:06:26,884 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2021-12-14 14:06:26,884 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 14:06:26,884 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 14:06:26,906 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2021-12-14 14:06:27,100 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable1 [2021-12-14 14:06:27,101 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 14:06:27,101 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 14:06:27,101 INFO L85 PathProgramCache]: Analyzing trace with hash -1769091626, now seen corresponding path program 1 times [2021-12-14 14:06:27,102 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 14:06:27,103 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1560095014] [2021-12-14 14:06:27,103 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:06:27,103 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 14:06:27,114 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-14 14:06:27,114 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1114279348] [2021-12-14 14:06:27,115 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:06:27,115 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:06:27,115 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 14:06:27,116 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) [2021-12-14 14:06:27,147 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2021-12-14 14:06:27,187 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:06:27,188 INFO L263 TraceCheckSpWp]: Trace formula consists of 69 conjuncts, 9 conjunts are in the unsatisfiable core [2021-12-14 14:06:27,190 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 14:06:27,430 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-12-14 14:06:27,431 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-14 14:06:27,431 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 14:06:27,431 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1560095014] [2021-12-14 14:06:27,431 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-14 14:06:27,432 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1114279348] [2021-12-14 14:06:27,432 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1114279348] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-14 14:06:27,432 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-14 14:06:27,432 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-12-14 14:06:27,432 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [709464460] [2021-12-14 14:06:27,433 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-14 14:06:27,433 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-12-14 14:06:27,433 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 14:06:27,434 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-12-14 14:06:27,434 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-12-14 14:06:27,434 INFO L87 Difference]: Start difference. First operand 30 states and 39 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2021-12-14 14:06:29,935 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.75s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2021-12-14 14:06:31,225 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.27s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2021-12-14 14:06:31,251 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 14:06:31,251 INFO L93 Difference]: Finished difference Result 49 states and 66 transitions. [2021-12-14 14:06:31,251 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-12-14 14:06:31,252 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 19 [2021-12-14 14:06:31,252 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 14:06:31,253 INFO L225 Difference]: With dead ends: 49 [2021-12-14 14:06:31,253 INFO L226 Difference]: Without dead ends: 47 [2021-12-14 14:06:31,253 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2021-12-14 14:06:31,254 INFO L933 BasicCegarLoop]: 29 mSDtfsCounter, 16 mSDsluCounter, 81 mSDsCounter, 0 mSdLazyCounter, 46 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 110 SdHoareTripleChecker+Invalid, 49 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 46 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.8s IncrementalHoareTripleChecker+Time [2021-12-14 14:06:31,255 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [19 Valid, 110 Invalid, 49 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 46 Invalid, 0 Unknown, 0 Unchecked, 3.8s Time] [2021-12-14 14:06:31,255 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2021-12-14 14:06:31,262 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 46. [2021-12-14 14:06:31,263 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 33 states have (on average 1.393939393939394) internal successors, (46), 34 states have internal predecessors, (46), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2021-12-14 14:06:31,264 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 63 transitions. [2021-12-14 14:06:31,264 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 63 transitions. Word has length 19 [2021-12-14 14:06:31,265 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 14:06:31,265 INFO L470 AbstractCegarLoop]: Abstraction has 46 states and 63 transitions. [2021-12-14 14:06:31,265 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2021-12-14 14:06:31,265 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 63 transitions. [2021-12-14 14:06:31,266 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2021-12-14 14:06:31,266 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 14:06:31,266 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 14:06:31,273 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2021-12-14 14:06:31,470 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:06:31,470 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 14:06:31,471 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 14:06:31,471 INFO L85 PathProgramCache]: Analyzing trace with hash -82041861, now seen corresponding path program 1 times [2021-12-14 14:06:31,471 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 14:06:31,471 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1720748765] [2021-12-14 14:06:31,471 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:06:31,471 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 14:06:31,478 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-14 14:06:31,478 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1170681958] [2021-12-14 14:06:31,479 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:06:31,479 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:06:31,479 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 14:06:31,480 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) [2021-12-14 14:06:31,484 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2021-12-14 14:06:31,518 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:06:31,519 INFO L263 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 10 conjunts are in the unsatisfiable core [2021-12-14 14:06:31,521 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 14:06:31,639 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-12-14 14:06:31,640 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 14:06:31,821 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-12-14 14:06:31,821 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 14:06:31,821 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1720748765] [2021-12-14 14:06:31,821 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-14 14:06:31,822 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1170681958] [2021-12-14 14:06:31,822 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1170681958] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-14 14:06:31,822 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-14 14:06:31,822 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 10 [2021-12-14 14:06:31,823 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1294507945] [2021-12-14 14:06:31,824 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-14 14:06:31,824 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2021-12-14 14:06:31,825 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 14:06:31,825 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2021-12-14 14:06:31,826 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=67, Unknown=0, NotChecked=0, Total=90 [2021-12-14 14:06:31,826 INFO L87 Difference]: Start difference. First operand 46 states and 63 transitions. Second operand has 10 states, 9 states have (on average 2.0) internal successors, (18), 7 states have internal predecessors, (18), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 3 states have call predecessors, (4), 1 states have call successors, (4) [2021-12-14 14:06:31,946 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 14:06:31,947 INFO L93 Difference]: Finished difference Result 53 states and 69 transitions. [2021-12-14 14:06:31,947 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2021-12-14 14:06:31,947 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 2.0) internal successors, (18), 7 states have internal predecessors, (18), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 3 states have call predecessors, (4), 1 states have call successors, (4) Word has length 25 [2021-12-14 14:06:31,948 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 14:06:31,948 INFO L225 Difference]: With dead ends: 53 [2021-12-14 14:06:31,949 INFO L226 Difference]: Without dead ends: 48 [2021-12-14 14:06:31,949 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 39 SyntacticMatches, 1 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=41, Invalid=115, Unknown=0, NotChecked=0, Total=156 [2021-12-14 14:06:31,950 INFO L933 BasicCegarLoop]: 25 mSDtfsCounter, 24 mSDsluCounter, 136 mSDsCounter, 0 mSdLazyCounter, 83 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 161 SdHoareTripleChecker+Invalid, 91 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 83 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-14 14:06:31,950 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [26 Valid, 161 Invalid, 91 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 83 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-14 14:06:31,951 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2021-12-14 14:06:31,956 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 32. [2021-12-14 14:06:31,956 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 23 states have (on average 1.2173913043478262) internal successors, (28), 23 states have internal predecessors, (28), 6 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2021-12-14 14:06:31,957 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 39 transitions. [2021-12-14 14:06:31,957 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 39 transitions. Word has length 25 [2021-12-14 14:06:31,957 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 14:06:31,957 INFO L470 AbstractCegarLoop]: Abstraction has 32 states and 39 transitions. [2021-12-14 14:06:31,957 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 2.0) internal successors, (18), 7 states have internal predecessors, (18), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 3 states have call predecessors, (4), 1 states have call successors, (4) [2021-12-14 14:06:31,958 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 39 transitions. [2021-12-14 14:06:31,958 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2021-12-14 14:06:31,959 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 14:06:31,959 INFO L514 BasicCegarLoop]: trace histogram [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] [2021-12-14 14:06:31,980 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2021-12-14 14:06:32,175 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:06:32,175 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 14:06:32,176 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 14:06:32,176 INFO L85 PathProgramCache]: Analyzing trace with hash -1145481658, now seen corresponding path program 1 times [2021-12-14 14:06:32,176 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 14:06:32,176 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1102863120] [2021-12-14 14:06:32,177 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:06:32,177 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 14:06:32,184 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-14 14:06:32,184 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [967192170] [2021-12-14 14:06:32,184 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:06:32,187 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:06:32,187 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 14:06:32,188 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) [2021-12-14 14:06:32,193 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2021-12-14 14:06:32,226 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:06:32,226 INFO L263 TraceCheckSpWp]: Trace formula consists of 94 conjuncts, 5 conjunts are in the unsatisfiable core [2021-12-14 14:06:32,228 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 14:06:32,288 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-12-14 14:06:32,289 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-14 14:06:32,289 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 14:06:32,289 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1102863120] [2021-12-14 14:06:32,289 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-14 14:06:32,290 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [967192170] [2021-12-14 14:06:32,290 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [967192170] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-14 14:06:32,290 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-14 14:06:32,290 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2021-12-14 14:06:32,290 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [500117784] [2021-12-14 14:06:32,290 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-14 14:06:32,291 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-12-14 14:06:32,291 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 14:06:32,291 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-12-14 14:06:32,292 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2021-12-14 14:06:32,292 INFO L87 Difference]: Start difference. First operand 32 states and 39 transitions. Second operand has 5 states, 5 states have (on average 4.2) internal successors, (21), 4 states have internal predecessors, (21), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2021-12-14 14:06:32,315 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 14:06:32,315 INFO L93 Difference]: Finished difference Result 61 states and 75 transitions. [2021-12-14 14:06:32,315 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-12-14 14:06:32,316 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.2) internal successors, (21), 4 states have internal predecessors, (21), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 31 [2021-12-14 14:06:32,316 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 14:06:32,316 INFO L225 Difference]: With dead ends: 61 [2021-12-14 14:06:32,317 INFO L226 Difference]: Without dead ends: 40 [2021-12-14 14:06:32,317 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 30 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2021-12-14 14:06:32,318 INFO L933 BasicCegarLoop]: 34 mSDtfsCounter, 5 mSDsluCounter, 59 mSDsCounter, 0 mSdLazyCounter, 15 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 93 SdHoareTripleChecker+Invalid, 20 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 15 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-14 14:06:32,318 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [5 Valid, 93 Invalid, 20 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 15 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-14 14:06:32,319 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2021-12-14 14:06:32,324 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 40. [2021-12-14 14:06:32,324 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 40 states, 29 states have (on average 1.1724137931034482) internal successors, (34), 29 states have internal predecessors, (34), 7 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2021-12-14 14:06:32,325 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 47 transitions. [2021-12-14 14:06:32,325 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 47 transitions. Word has length 31 [2021-12-14 14:06:32,325 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 14:06:32,326 INFO L470 AbstractCegarLoop]: Abstraction has 40 states and 47 transitions. [2021-12-14 14:06:32,326 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.2) internal successors, (21), 4 states have internal predecessors, (21), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2021-12-14 14:06:32,326 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 47 transitions. [2021-12-14 14:06:32,327 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2021-12-14 14:06:32,327 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 14:06:32,327 INFO L514 BasicCegarLoop]: trace histogram [3, 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] [2021-12-14 14:06:32,348 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2021-12-14 14:06:32,535 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:06:32,536 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 14:06:32,536 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 14:06:32,536 INFO L85 PathProgramCache]: Analyzing trace with hash -1102972225, now seen corresponding path program 1 times [2021-12-14 14:06:32,536 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 14:06:32,536 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [56548948] [2021-12-14 14:06:32,536 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:06:32,537 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 14:06:32,545 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-14 14:06:32,546 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [593052767] [2021-12-14 14:06:32,546 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:06:32,546 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:06:32,546 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 14:06:32,547 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) [2021-12-14 14:06:32,550 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2021-12-14 14:06:32,585 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:06:32,586 INFO L263 TraceCheckSpWp]: Trace formula consists of 104 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-14 14:06:32,587 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 14:06:32,674 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-12-14 14:06:32,674 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 14:06:32,771 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2021-12-14 14:06:32,772 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 14:06:32,772 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [56548948] [2021-12-14 14:06:32,772 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-14 14:06:32,772 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [593052767] [2021-12-14 14:06:32,772 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [593052767] provided 1 perfect and 1 imperfect interpolant sequences [2021-12-14 14:06:32,773 INFO L186 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2021-12-14 14:06:32,773 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [5] total 10 [2021-12-14 14:06:32,773 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [871028261] [2021-12-14 14:06:32,773 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-14 14:06:32,773 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2021-12-14 14:06:32,774 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 14:06:32,774 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2021-12-14 14:06:32,775 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2021-12-14 14:06:32,775 INFO L87 Difference]: Start difference. First operand 40 states and 47 transitions. Second operand has 6 states, 6 states have (on average 3.6666666666666665) internal successors, (22), 6 states have internal predecessors, (22), 4 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2021-12-14 14:06:32,810 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 14:06:32,811 INFO L93 Difference]: Finished difference Result 70 states and 85 transitions. [2021-12-14 14:06:32,811 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-12-14 14:06:32,813 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 3.6666666666666665) internal successors, (22), 6 states have internal predecessors, (22), 4 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Word has length 37 [2021-12-14 14:06:32,814 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 14:06:32,817 INFO L225 Difference]: With dead ends: 70 [2021-12-14 14:06:32,817 INFO L226 Difference]: Without dead ends: 49 [2021-12-14 14:06:32,818 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 72 GetRequests, 64 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2021-12-14 14:06:32,818 INFO L933 BasicCegarLoop]: 34 mSDtfsCounter, 29 mSDsluCounter, 65 mSDsCounter, 0 mSdLazyCounter, 20 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 99 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 20 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-14 14:06:32,819 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [29 Valid, 99 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 20 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-14 14:06:32,819 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2021-12-14 14:06:32,825 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 48. [2021-12-14 14:06:32,826 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 35 states have (on average 1.1714285714285715) internal successors, (41), 35 states have internal predecessors, (41), 8 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2021-12-14 14:06:32,827 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 56 transitions. [2021-12-14 14:06:32,827 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 56 transitions. Word has length 37 [2021-12-14 14:06:32,827 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 14:06:32,827 INFO L470 AbstractCegarLoop]: Abstraction has 48 states and 56 transitions. [2021-12-14 14:06:32,827 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 3.6666666666666665) internal successors, (22), 6 states have internal predecessors, (22), 4 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2021-12-14 14:06:32,828 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 56 transitions. [2021-12-14 14:06:32,828 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2021-12-14 14:06:32,829 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 14:06:32,829 INFO L514 BasicCegarLoop]: trace histogram [3, 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] [2021-12-14 14:06:32,851 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2021-12-14 14:06:33,043 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:06:33,043 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 14:06:33,044 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 14:06:33,044 INFO L85 PathProgramCache]: Analyzing trace with hash 30895492, now seen corresponding path program 1 times [2021-12-14 14:06:33,045 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 14:06:33,045 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2144418341] [2021-12-14 14:06:33,045 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:06:33,045 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 14:06:33,051 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-14 14:06:33,052 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [136854719] [2021-12-14 14:06:33,052 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:06:33,052 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:06:33,052 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 14:06:33,053 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) [2021-12-14 14:06:33,061 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2021-12-14 14:06:33,088 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:06:33,089 INFO L263 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-14 14:06:33,090 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 14:06:33,174 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 6 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-12-14 14:06:33,174 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 14:06:33,283 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2021-12-14 14:06:33,284 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 14:06:33,284 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2144418341] [2021-12-14 14:06:33,284 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-14 14:06:33,284 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [136854719] [2021-12-14 14:06:33,284 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [136854719] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-14 14:06:33,285 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-14 14:06:33,285 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 6] total 10 [2021-12-14 14:06:33,285 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [906033169] [2021-12-14 14:06:33,285 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-14 14:06:33,286 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2021-12-14 14:06:33,286 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 14:06:33,286 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2021-12-14 14:06:33,286 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2021-12-14 14:06:33,286 INFO L87 Difference]: Start difference. First operand 48 states and 56 transitions. Second operand has 10 states, 10 states have (on average 4.4) internal successors, (44), 10 states have internal predecessors, (44), 7 states have call successors, (9), 5 states have call predecessors, (9), 4 states have return successors, (8), 6 states have call predecessors, (8), 6 states have call successors, (8) [2021-12-14 14:06:33,414 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 14:06:33,415 INFO L93 Difference]: Finished difference Result 125 states and 156 transitions. [2021-12-14 14:06:33,415 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2021-12-14 14:06:33,415 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 4.4) internal successors, (44), 10 states have internal predecessors, (44), 7 states have call successors, (9), 5 states have call predecessors, (9), 4 states have return successors, (8), 6 states have call predecessors, (8), 6 states have call successors, (8) Word has length 39 [2021-12-14 14:06:33,416 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 14:06:33,417 INFO L225 Difference]: With dead ends: 125 [2021-12-14 14:06:33,417 INFO L226 Difference]: Without dead ends: 104 [2021-12-14 14:06:33,417 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 80 GetRequests, 68 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=63, Invalid=119, Unknown=0, NotChecked=0, Total=182 [2021-12-14 14:06:33,418 INFO L933 BasicCegarLoop]: 42 mSDtfsCounter, 90 mSDsluCounter, 123 mSDsCounter, 0 mSdLazyCounter, 62 mSolverCounterSat, 42 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 90 SdHoareTripleChecker+Valid, 165 SdHoareTripleChecker+Invalid, 104 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 42 IncrementalHoareTripleChecker+Valid, 62 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-14 14:06:33,418 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [90 Valid, 165 Invalid, 104 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [42 Valid, 62 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-14 14:06:33,419 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 104 states. [2021-12-14 14:06:33,431 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 104 to 91. [2021-12-14 14:06:33,431 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 91 states, 67 states have (on average 1.2238805970149254) internal successors, (82), 68 states have internal predecessors, (82), 16 states have call successors, (16), 8 states have call predecessors, (16), 7 states have return successors, (15), 14 states have call predecessors, (15), 15 states have call successors, (15) [2021-12-14 14:06:33,432 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 113 transitions. [2021-12-14 14:06:33,432 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 113 transitions. Word has length 39 [2021-12-14 14:06:33,433 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 14:06:33,433 INFO L470 AbstractCegarLoop]: Abstraction has 91 states and 113 transitions. [2021-12-14 14:06:33,433 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 4.4) internal successors, (44), 10 states have internal predecessors, (44), 7 states have call successors, (9), 5 states have call predecessors, (9), 4 states have return successors, (8), 6 states have call predecessors, (8), 6 states have call successors, (8) [2021-12-14 14:06:33,433 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 113 transitions. [2021-12-14 14:06:33,434 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2021-12-14 14:06:33,434 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 14:06:33,435 INFO L514 BasicCegarLoop]: trace histogram [4, 3, 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, 1] [2021-12-14 14:06:33,453 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2021-12-14 14:06:33,643 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:06:33,644 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 14:06:33,644 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 14:06:33,644 INFO L85 PathProgramCache]: Analyzing trace with hash -798356602, now seen corresponding path program 1 times [2021-12-14 14:06:33,644 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 14:06:33,644 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1596724368] [2021-12-14 14:06:33,644 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:06:33,645 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 14:06:33,651 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-14 14:06:33,652 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1144808227] [2021-12-14 14:06:33,652 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:06:33,652 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:06:33,652 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 14:06:33,655 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) [2021-12-14 14:06:33,656 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2021-12-14 14:06:33,686 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:06:33,687 INFO L263 TraceCheckSpWp]: Trace formula consists of 114 conjuncts, 3 conjunts are in the unsatisfiable core [2021-12-14 14:06:33,688 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 14:06:33,781 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2021-12-14 14:06:33,781 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-14 14:06:33,782 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 14:06:33,782 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1596724368] [2021-12-14 14:06:33,782 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-14 14:06:33,782 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1144808227] [2021-12-14 14:06:33,782 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1144808227] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-14 14:06:33,782 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-14 14:06:33,782 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2021-12-14 14:06:33,783 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [165975019] [2021-12-14 14:06:33,783 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-14 14:06:33,784 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2021-12-14 14:06:33,784 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 14:06:33,785 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-12-14 14:06:33,785 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2021-12-14 14:06:33,785 INFO L87 Difference]: Start difference. First operand 91 states and 113 transitions. Second operand has 4 states, 4 states have (on average 5.75) internal successors, (23), 4 states have internal predecessors, (23), 4 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2021-12-14 14:06:33,818 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 14:06:33,818 INFO L93 Difference]: Finished difference Result 154 states and 198 transitions. [2021-12-14 14:06:33,818 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2021-12-14 14:06:33,819 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 5.75) internal successors, (23), 4 states have internal predecessors, (23), 4 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) Word has length 43 [2021-12-14 14:06:33,819 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 14:06:33,822 INFO L225 Difference]: With dead ends: 154 [2021-12-14 14:06:33,822 INFO L226 Difference]: Without dead ends: 115 [2021-12-14 14:06:33,823 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 40 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2021-12-14 14:06:33,824 INFO L933 BasicCegarLoop]: 50 mSDtfsCounter, 23 mSDsluCounter, 41 mSDsCounter, 0 mSdLazyCounter, 19 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 91 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 19 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-14 14:06:33,825 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [27 Valid, 91 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 19 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-14 14:06:33,825 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 115 states. [2021-12-14 14:06:33,856 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 115 to 105. [2021-12-14 14:06:33,857 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 105 states, 78 states have (on average 1.2307692307692308) internal successors, (96), 79 states have internal predecessors, (96), 19 states have call successors, (19), 8 states have call predecessors, (19), 7 states have return successors, (18), 17 states have call predecessors, (18), 18 states have call successors, (18) [2021-12-14 14:06:33,862 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 105 states to 105 states and 133 transitions. [2021-12-14 14:06:33,862 INFO L78 Accepts]: Start accepts. Automaton has 105 states and 133 transitions. Word has length 43 [2021-12-14 14:06:33,863 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 14:06:33,864 INFO L470 AbstractCegarLoop]: Abstraction has 105 states and 133 transitions. [2021-12-14 14:06:33,864 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 5.75) internal successors, (23), 4 states have internal predecessors, (23), 4 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2021-12-14 14:06:33,864 INFO L276 IsEmpty]: Start isEmpty. Operand 105 states and 133 transitions. [2021-12-14 14:06:33,866 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2021-12-14 14:06:33,869 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 14:06:33,869 INFO L514 BasicCegarLoop]: trace histogram [4, 3, 3, 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] [2021-12-14 14:06:33,892 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2021-12-14 14:06:34,084 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2021-12-14 14:06:34,085 INFO L402 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 14:06:34,085 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 14:06:34,085 INFO L85 PathProgramCache]: Analyzing trace with hash -1023958197, now seen corresponding path program 1 times [2021-12-14 14:06:34,085 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 14:06:34,085 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [386947942] [2021-12-14 14:06:34,085 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:06:34,086 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 14:06:34,092 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-14 14:06:34,092 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1211541430] [2021-12-14 14:06:34,092 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:06:34,092 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:06:34,092 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 14:06:34,109 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) [2021-12-14 14:06:34,115 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2021-12-14 14:06:34,160 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:06:34,163 INFO L263 TraceCheckSpWp]: Trace formula consists of 123 conjuncts, 9 conjunts are in the unsatisfiable core [2021-12-14 14:06:34,168 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 14:06:34,276 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 8 proven. 14 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-12-14 14:06:34,276 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 14:06:34,400 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2021-12-14 14:06:34,400 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 14:06:34,401 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [386947942] [2021-12-14 14:06:34,401 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-14 14:06:34,401 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1211541430] [2021-12-14 14:06:34,401 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1211541430] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-14 14:06:34,401 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-14 14:06:34,401 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 7] total 12 [2021-12-14 14:06:34,402 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [155280490] [2021-12-14 14:06:34,402 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-14 14:06:34,402 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2021-12-14 14:06:34,402 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 14:06:34,403 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2021-12-14 14:06:34,403 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=82, Unknown=0, NotChecked=0, Total=132 [2021-12-14 14:06:34,403 INFO L87 Difference]: Start difference. First operand 105 states and 133 transitions. Second operand has 12 states, 12 states have (on average 4.25) internal successors, (51), 12 states have internal predecessors, (51), 9 states have call successors, (11), 6 states have call predecessors, (11), 5 states have return successors, (10), 8 states have call predecessors, (10), 8 states have call successors, (10) [2021-12-14 14:06:34,584 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 14:06:34,585 INFO L93 Difference]: Finished difference Result 215 states and 279 transitions. [2021-12-14 14:06:34,585 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2021-12-14 14:06:34,585 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 4.25) internal successors, (51), 12 states have internal predecessors, (51), 9 states have call successors, (11), 6 states have call predecessors, (11), 5 states have return successors, (10), 8 states have call predecessors, (10), 8 states have call successors, (10) Word has length 45 [2021-12-14 14:06:34,586 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 14:06:34,587 INFO L225 Difference]: With dead ends: 215 [2021-12-14 14:06:34,587 INFO L226 Difference]: Without dead ends: 168 [2021-12-14 14:06:34,587 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 93 GetRequests, 78 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=92, Invalid=180, Unknown=0, NotChecked=0, Total=272 [2021-12-14 14:06:34,588 INFO L933 BasicCegarLoop]: 47 mSDtfsCounter, 140 mSDsluCounter, 152 mSDsCounter, 0 mSdLazyCounter, 88 mSolverCounterSat, 67 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 140 SdHoareTripleChecker+Valid, 199 SdHoareTripleChecker+Invalid, 155 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 67 IncrementalHoareTripleChecker+Valid, 88 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-14 14:06:34,588 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [140 Valid, 199 Invalid, 155 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [67 Valid, 88 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-14 14:06:34,589 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 168 states. [2021-12-14 14:06:34,602 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 168 to 149. [2021-12-14 14:06:34,602 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 149 states, 111 states have (on average 1.2432432432432432) internal successors, (138), 112 states have internal predecessors, (138), 28 states have call successors, (28), 10 states have call predecessors, (28), 9 states have return successors, (27), 26 states have call predecessors, (27), 27 states have call successors, (27) [2021-12-14 14:06:34,604 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 149 states to 149 states and 193 transitions. [2021-12-14 14:06:34,604 INFO L78 Accepts]: Start accepts. Automaton has 149 states and 193 transitions. Word has length 45 [2021-12-14 14:06:34,604 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 14:06:34,604 INFO L470 AbstractCegarLoop]: Abstraction has 149 states and 193 transitions. [2021-12-14 14:06:34,605 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 4.25) internal successors, (51), 12 states have internal predecessors, (51), 9 states have call successors, (11), 6 states have call predecessors, (11), 5 states have return successors, (10), 8 states have call predecessors, (10), 8 states have call successors, (10) [2021-12-14 14:06:34,605 INFO L276 IsEmpty]: Start isEmpty. Operand 149 states and 193 transitions. [2021-12-14 14:06:34,606 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2021-12-14 14:06:34,606 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 14:06:34,606 INFO L514 BasicCegarLoop]: trace histogram [5, 4, 4, 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] [2021-12-14 14:06:34,629 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2021-12-14 14:06:34,815 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:06:34,815 INFO L402 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 14:06:34,816 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 14:06:34,816 INFO L85 PathProgramCache]: Analyzing trace with hash -1104536814, now seen corresponding path program 1 times [2021-12-14 14:06:34,816 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 14:06:34,816 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [634303186] [2021-12-14 14:06:34,816 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:06:34,816 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 14:06:34,823 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-14 14:06:34,823 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [199759333] [2021-12-14 14:06:34,823 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:06:34,823 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:06:34,824 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 14:06:34,824 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) [2021-12-14 14:06:34,850 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2021-12-14 14:06:34,867 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:06:34,868 INFO L263 TraceCheckSpWp]: Trace formula consists of 133 conjuncts, 11 conjunts are in the unsatisfiable core [2021-12-14 14:06:34,869 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 14:06:34,974 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 8 proven. 30 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-12-14 14:06:34,974 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 14:06:35,097 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 8 proven. 6 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2021-12-14 14:06:35,098 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 14:06:35,098 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [634303186] [2021-12-14 14:06:35,098 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-14 14:06:35,098 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [199759333] [2021-12-14 14:06:35,099 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [199759333] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-14 14:06:35,099 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-14 14:06:35,099 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 8] total 14 [2021-12-14 14:06:35,099 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [327580257] [2021-12-14 14:06:35,099 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-14 14:06:35,100 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2021-12-14 14:06:35,100 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 14:06:35,100 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2021-12-14 14:06:35,101 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2021-12-14 14:06:35,101 INFO L87 Difference]: Start difference. First operand 149 states and 193 transitions. Second operand has 14 states, 14 states have (on average 4.142857142857143) internal successors, (58), 14 states have internal predecessors, (58), 11 states have call successors, (13), 7 states have call predecessors, (13), 6 states have return successors, (12), 10 states have call predecessors, (12), 10 states have call successors, (12) [2021-12-14 14:06:35,332 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 14:06:35,333 INFO L93 Difference]: Finished difference Result 207 states and 274 transitions. [2021-12-14 14:06:35,333 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2021-12-14 14:06:35,333 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 4.142857142857143) internal successors, (58), 14 states have internal predecessors, (58), 11 states have call successors, (13), 7 states have call predecessors, (13), 6 states have return successors, (12), 10 states have call predecessors, (12), 10 states have call successors, (12) Word has length 51 [2021-12-14 14:06:35,335 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 14:06:35,336 INFO L225 Difference]: With dead ends: 207 [2021-12-14 14:06:35,337 INFO L226 Difference]: Without dead ends: 202 [2021-12-14 14:06:35,337 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 106 GetRequests, 88 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 34 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=130, Invalid=250, Unknown=0, NotChecked=0, Total=380 [2021-12-14 14:06:35,338 INFO L933 BasicCegarLoop]: 53 mSDtfsCounter, 242 mSDsluCounter, 223 mSDsCounter, 0 mSdLazyCounter, 113 mSolverCounterSat, 137 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 242 SdHoareTripleChecker+Valid, 276 SdHoareTripleChecker+Invalid, 250 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 137 IncrementalHoareTripleChecker+Valid, 113 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-12-14 14:06:35,338 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [242 Valid, 276 Invalid, 250 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [137 Valid, 113 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-12-14 14:06:35,339 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 202 states. [2021-12-14 14:06:35,359 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 202 to 194. [2021-12-14 14:06:35,359 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 194 states, 144 states have (on average 1.2361111111111112) internal successors, (178), 148 states have internal predecessors, (178), 38 states have call successors, (38), 12 states have call predecessors, (38), 11 states have return successors, (37), 33 states have call predecessors, (37), 37 states have call successors, (37) [2021-12-14 14:06:35,361 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 194 states to 194 states and 253 transitions. [2021-12-14 14:06:35,361 INFO L78 Accepts]: Start accepts. Automaton has 194 states and 253 transitions. Word has length 51 [2021-12-14 14:06:35,363 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 14:06:35,363 INFO L470 AbstractCegarLoop]: Abstraction has 194 states and 253 transitions. [2021-12-14 14:06:35,364 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 4.142857142857143) internal successors, (58), 14 states have internal predecessors, (58), 11 states have call successors, (13), 7 states have call predecessors, (13), 6 states have return successors, (12), 10 states have call predecessors, (12), 10 states have call successors, (12) [2021-12-14 14:06:35,364 INFO L276 IsEmpty]: Start isEmpty. Operand 194 states and 253 transitions. [2021-12-14 14:06:35,368 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2021-12-14 14:06:35,368 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 14:06:35,368 INFO L514 BasicCegarLoop]: trace histogram [9, 8, 8, 5, 4, 4, 4, 3, 3, 3, 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] [2021-12-14 14:06:35,394 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2021-12-14 14:06:35,588 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2021-12-14 14:06:35,588 INFO L402 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 14:06:35,588 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 14:06:35,588 INFO L85 PathProgramCache]: Analyzing trace with hash 540498080, now seen corresponding path program 1 times [2021-12-14 14:06:35,589 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 14:06:35,589 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1325056415] [2021-12-14 14:06:35,589 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:06:35,589 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 14:06:35,595 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-14 14:06:35,596 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [391992681] [2021-12-14 14:06:35,596 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:06:35,596 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:06:35,596 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 14:06:35,597 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) [2021-12-14 14:06:35,598 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2021-12-14 14:06:35,645 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:06:35,646 INFO L263 TraceCheckSpWp]: Trace formula consists of 215 conjuncts, 4 conjunts are in the unsatisfiable core [2021-12-14 14:06:35,650 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 14:06:35,780 INFO L134 CoverageAnalysis]: Checked inductivity of 180 backedges. 64 proven. 12 refuted. 0 times theorem prover too weak. 104 trivial. 0 not checked. [2021-12-14 14:06:35,780 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 14:06:35,926 INFO L134 CoverageAnalysis]: Checked inductivity of 180 backedges. 38 proven. 12 refuted. 0 times theorem prover too weak. 130 trivial. 0 not checked. [2021-12-14 14:06:35,926 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 14:06:35,927 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1325056415] [2021-12-14 14:06:35,927 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-14 14:06:35,927 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [391992681] [2021-12-14 14:06:35,927 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [391992681] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-14 14:06:35,927 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-14 14:06:35,927 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 4 [2021-12-14 14:06:35,928 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [455049677] [2021-12-14 14:06:35,928 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-14 14:06:35,928 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2021-12-14 14:06:35,928 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 14:06:35,929 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-12-14 14:06:35,929 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-12-14 14:06:35,929 INFO L87 Difference]: Start difference. First operand 194 states and 253 transitions. Second operand has 4 states, 4 states have (on average 9.0) internal successors, (36), 4 states have internal predecessors, (36), 4 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) [2021-12-14 14:06:35,989 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 14:06:35,989 INFO L93 Difference]: Finished difference Result 498 states and 693 transitions. [2021-12-14 14:06:35,989 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-12-14 14:06:35,990 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 9.0) internal successors, (36), 4 states have internal predecessors, (36), 4 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) Word has length 87 [2021-12-14 14:06:35,990 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 14:06:35,993 INFO L225 Difference]: With dead ends: 498 [2021-12-14 14:06:35,993 INFO L226 Difference]: Without dead ends: 355 [2021-12-14 14:06:35,995 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 173 GetRequests, 169 SyntacticMatches, 1 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2021-12-14 14:06:35,996 INFO L933 BasicCegarLoop]: 67 mSDtfsCounter, 16 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 21 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 151 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 21 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-14 14:06:35,996 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [18 Valid, 151 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 21 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-14 14:06:35,997 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 355 states. [2021-12-14 14:06:36,040 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 355 to 338. [2021-12-14 14:06:36,041 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 338 states, 254 states have (on average 1.2677165354330708) internal successors, (322), 260 states have internal predecessors, (322), 72 states have call successors, (72), 12 states have call predecessors, (72), 11 states have return successors, (71), 65 states have call predecessors, (71), 71 states have call successors, (71) [2021-12-14 14:06:36,042 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 338 states to 338 states and 465 transitions. [2021-12-14 14:06:36,043 INFO L78 Accepts]: Start accepts. Automaton has 338 states and 465 transitions. Word has length 87 [2021-12-14 14:06:36,043 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 14:06:36,043 INFO L470 AbstractCegarLoop]: Abstraction has 338 states and 465 transitions. [2021-12-14 14:06:36,043 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 9.0) internal successors, (36), 4 states have internal predecessors, (36), 4 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) [2021-12-14 14:06:36,043 INFO L276 IsEmpty]: Start isEmpty. Operand 338 states and 465 transitions. [2021-12-14 14:06:36,046 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2021-12-14 14:06:36,046 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 14:06:36,046 INFO L514 BasicCegarLoop]: trace histogram [9, 8, 8, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 14:06:36,071 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2021-12-14 14:06:36,259 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2021-12-14 14:06:36,259 INFO L402 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 14:06:36,260 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 14:06:36,260 INFO L85 PathProgramCache]: Analyzing trace with hash -134976430, now seen corresponding path program 2 times [2021-12-14 14:06:36,260 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 14:06:36,260 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2061427914] [2021-12-14 14:06:36,260 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:06:36,261 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 14:06:36,268 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-14 14:06:36,268 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1107592253] [2021-12-14 14:06:36,268 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2021-12-14 14:06:36,268 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:06:36,268 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 14:06:36,269 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) [2021-12-14 14:06:36,274 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2021-12-14 14:06:36,321 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-12-14 14:06:36,321 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-14 14:06:36,322 INFO L263 TraceCheckSpWp]: Trace formula consists of 215 conjuncts, 17 conjunts are in the unsatisfiable core [2021-12-14 14:06:36,327 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 14:06:36,502 INFO L134 CoverageAnalysis]: Checked inductivity of 176 backedges. 58 proven. 110 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2021-12-14 14:06:36,502 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 14:06:36,742 INFO L134 CoverageAnalysis]: Checked inductivity of 176 backedges. 32 proven. 26 refuted. 0 times theorem prover too weak. 118 trivial. 0 not checked. [2021-12-14 14:06:36,743 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 14:06:36,743 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2061427914] [2021-12-14 14:06:36,743 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-14 14:06:36,743 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1107592253] [2021-12-14 14:06:36,743 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1107592253] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-14 14:06:36,743 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-14 14:06:36,743 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 11] total 20 [2021-12-14 14:06:36,743 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [939781987] [2021-12-14 14:06:36,743 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-14 14:06:36,744 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2021-12-14 14:06:36,744 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 14:06:36,744 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2021-12-14 14:06:36,744 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=158, Invalid=222, Unknown=0, NotChecked=0, Total=380 [2021-12-14 14:06:36,745 INFO L87 Difference]: Start difference. First operand 338 states and 465 transitions. Second operand has 20 states, 20 states have (on average 4.65) internal successors, (93), 20 states have internal predecessors, (93), 17 states have call successors, (21), 10 states have call predecessors, (21), 10 states have return successors, (20), 17 states have call predecessors, (20), 17 states have call successors, (20) [2021-12-14 14:06:37,292 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 14:06:37,292 INFO L93 Difference]: Finished difference Result 981 states and 1419 transitions. [2021-12-14 14:06:37,293 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2021-12-14 14:06:37,293 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 4.65) internal successors, (93), 20 states have internal predecessors, (93), 17 states have call successors, (21), 10 states have call predecessors, (21), 10 states have return successors, (20), 17 states have call predecessors, (20), 17 states have call successors, (20) Word has length 87 [2021-12-14 14:06:37,294 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 14:06:37,300 INFO L225 Difference]: With dead ends: 981 [2021-12-14 14:06:37,300 INFO L226 Difference]: Without dead ends: 838 [2021-12-14 14:06:37,301 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 186 GetRequests, 154 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 134 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=403, Invalid=719, Unknown=0, NotChecked=0, Total=1122 [2021-12-14 14:06:37,302 INFO L933 BasicCegarLoop]: 71 mSDtfsCounter, 414 mSDsluCounter, 353 mSDsCounter, 0 mSdLazyCounter, 237 mSolverCounterSat, 241 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 414 SdHoareTripleChecker+Valid, 424 SdHoareTripleChecker+Invalid, 478 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 241 IncrementalHoareTripleChecker+Valid, 237 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2021-12-14 14:06:37,302 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [414 Valid, 424 Invalid, 478 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [241 Valid, 237 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2021-12-14 14:06:37,303 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 838 states. [2021-12-14 14:06:37,380 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 838 to 789. [2021-12-14 14:06:37,382 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 789 states, 596 states have (on average 1.2684563758389262) internal successors, (756), 605 states have internal predecessors, (756), 175 states have call successors, (175), 18 states have call predecessors, (175), 17 states have return successors, (174), 165 states have call predecessors, (174), 174 states have call successors, (174) [2021-12-14 14:06:37,386 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 789 states to 789 states and 1105 transitions. [2021-12-14 14:06:37,386 INFO L78 Accepts]: Start accepts. Automaton has 789 states and 1105 transitions. Word has length 87 [2021-12-14 14:06:37,387 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 14:06:37,387 INFO L470 AbstractCegarLoop]: Abstraction has 789 states and 1105 transitions. [2021-12-14 14:06:37,388 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 4.65) internal successors, (93), 20 states have internal predecessors, (93), 17 states have call successors, (21), 10 states have call predecessors, (21), 10 states have return successors, (20), 17 states have call predecessors, (20), 17 states have call successors, (20) [2021-12-14 14:06:37,388 INFO L276 IsEmpty]: Start isEmpty. Operand 789 states and 1105 transitions. [2021-12-14 14:06:37,390 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 94 [2021-12-14 14:06:37,390 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 14:06:37,390 INFO L514 BasicCegarLoop]: trace histogram [10, 9, 9, 4, 4, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 14:06:37,417 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2021-12-14 14:06:37,615 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2021-12-14 14:06:37,615 INFO L402 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 14:06:37,616 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 14:06:37,616 INFO L85 PathProgramCache]: Analyzing trace with hash 2132027339, now seen corresponding path program 1 times [2021-12-14 14:06:37,616 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 14:06:37,616 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1521900640] [2021-12-14 14:06:37,616 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:06:37,616 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 14:06:37,622 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-14 14:06:37,622 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [456555558] [2021-12-14 14:06:37,623 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:06:37,623 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:06:37,623 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 14:06:37,625 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) [2021-12-14 14:06:37,626 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2021-12-14 14:06:37,670 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:06:37,672 INFO L263 TraceCheckSpWp]: Trace formula consists of 225 conjuncts, 21 conjunts are in the unsatisfiable core [2021-12-14 14:06:37,674 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 14:06:37,922 INFO L134 CoverageAnalysis]: Checked inductivity of 216 backedges. 22 proven. 190 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-12-14 14:06:37,923 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 14:06:38,230 INFO L134 CoverageAnalysis]: Checked inductivity of 216 backedges. 22 proven. 46 refuted. 0 times theorem prover too weak. 148 trivial. 0 not checked. [2021-12-14 14:06:38,230 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 14:06:38,230 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1521900640] [2021-12-14 14:06:38,230 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-14 14:06:38,230 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [456555558] [2021-12-14 14:06:38,230 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [456555558] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-14 14:06:38,230 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-14 14:06:38,231 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 13] total 24 [2021-12-14 14:06:38,231 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1683270367] [2021-12-14 14:06:38,231 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-14 14:06:38,231 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2021-12-14 14:06:38,231 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 14:06:38,232 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2021-12-14 14:06:38,232 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=236, Invalid=316, Unknown=0, NotChecked=0, Total=552 [2021-12-14 14:06:38,232 INFO L87 Difference]: Start difference. First operand 789 states and 1105 transitions. Second operand has 24 states, 24 states have (on average 4.375) internal successors, (105), 24 states have internal predecessors, (105), 21 states have call successors, (23), 12 states have call predecessors, (23), 11 states have return successors, (22), 20 states have call predecessors, (22), 20 states have call successors, (22) [2021-12-14 14:06:38,917 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 14:06:38,917 INFO L93 Difference]: Finished difference Result 1281 states and 1795 transitions. [2021-12-14 14:06:38,918 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2021-12-14 14:06:38,918 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 24 states have (on average 4.375) internal successors, (105), 24 states have internal predecessors, (105), 21 states have call successors, (23), 12 states have call predecessors, (23), 11 states have return successors, (22), 20 states have call predecessors, (22), 20 states have call successors, (22) Word has length 93 [2021-12-14 14:06:38,918 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 14:06:38,922 INFO L225 Difference]: With dead ends: 1281 [2021-12-14 14:06:38,922 INFO L226 Difference]: Without dead ends: 791 [2021-12-14 14:06:38,924 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 201 GetRequests, 162 SyntacticMatches, 0 SemanticMatches, 39 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 200 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=584, Invalid=1056, Unknown=0, NotChecked=0, Total=1640 [2021-12-14 14:06:38,925 INFO L933 BasicCegarLoop]: 83 mSDtfsCounter, 405 mSDsluCounter, 359 mSDsCounter, 0 mSdLazyCounter, 352 mSolverCounterSat, 227 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 405 SdHoareTripleChecker+Valid, 442 SdHoareTripleChecker+Invalid, 579 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 227 IncrementalHoareTripleChecker+Valid, 352 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2021-12-14 14:06:38,926 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [405 Valid, 442 Invalid, 579 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [227 Valid, 352 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2021-12-14 14:06:38,927 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 791 states. [2021-12-14 14:06:38,993 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 791 to 736. [2021-12-14 14:06:38,994 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 736 states, 552 states have (on average 1.2210144927536233) internal successors, (674), 556 states have internal predecessors, (674), 162 states have call successors, (162), 22 states have call predecessors, (162), 21 states have return successors, (161), 157 states have call predecessors, (161), 161 states have call successors, (161) [2021-12-14 14:06:38,997 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 736 states to 736 states and 997 transitions. [2021-12-14 14:06:38,997 INFO L78 Accepts]: Start accepts. Automaton has 736 states and 997 transitions. Word has length 93 [2021-12-14 14:06:38,998 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 14:06:38,998 INFO L470 AbstractCegarLoop]: Abstraction has 736 states and 997 transitions. [2021-12-14 14:06:38,998 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 24 states have (on average 4.375) internal successors, (105), 24 states have internal predecessors, (105), 21 states have call successors, (23), 12 states have call predecessors, (23), 11 states have return successors, (22), 20 states have call predecessors, (22), 20 states have call successors, (22) [2021-12-14 14:06:38,998 INFO L276 IsEmpty]: Start isEmpty. Operand 736 states and 997 transitions. [2021-12-14 14:06:39,000 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 100 [2021-12-14 14:06:39,000 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 14:06:39,000 INFO L514 BasicCegarLoop]: trace histogram [11, 10, 10, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 14:06:39,025 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2021-12-14 14:06:39,223 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2021-12-14 14:06:39,223 INFO L402 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 14:06:39,223 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 14:06:39,223 INFO L85 PathProgramCache]: Analyzing trace with hash 519126930, now seen corresponding path program 1 times [2021-12-14 14:06:39,224 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 14:06:39,224 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1662627940] [2021-12-14 14:06:39,224 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:06:39,224 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 14:06:39,230 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-14 14:06:39,230 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1069796510] [2021-12-14 14:06:39,230 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:06:39,230 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:06:39,231 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 14:06:39,233 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) [2021-12-14 14:06:39,234 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2021-12-14 14:06:39,283 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:06:39,285 INFO L263 TraceCheckSpWp]: Trace formula consists of 235 conjuncts, 23 conjunts are in the unsatisfiable core [2021-12-14 14:06:39,287 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 14:06:39,513 INFO L134 CoverageAnalysis]: Checked inductivity of 260 backedges. 20 proven. 236 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-12-14 14:06:39,513 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 14:06:39,854 INFO L134 CoverageAnalysis]: Checked inductivity of 260 backedges. 20 proven. 56 refuted. 0 times theorem prover too weak. 184 trivial. 0 not checked. [2021-12-14 14:06:39,854 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 14:06:39,854 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1662627940] [2021-12-14 14:06:39,855 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-14 14:06:39,855 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1069796510] [2021-12-14 14:06:39,855 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1069796510] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-14 14:06:39,855 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-14 14:06:39,855 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 14] total 26 [2021-12-14 14:06:39,855 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2070085908] [2021-12-14 14:06:39,856 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-14 14:06:39,857 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2021-12-14 14:06:39,857 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 14:06:39,857 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2021-12-14 14:06:39,858 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=281, Invalid=369, Unknown=0, NotChecked=0, Total=650 [2021-12-14 14:06:39,858 INFO L87 Difference]: Start difference. First operand 736 states and 997 transitions. Second operand has 26 states, 26 states have (on average 4.3076923076923075) internal successors, (112), 26 states have internal predecessors, (112), 23 states have call successors, (25), 13 states have call predecessors, (25), 12 states have return successors, (24), 22 states have call predecessors, (24), 22 states have call successors, (24) [2021-12-14 14:06:40,612 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 14:06:40,612 INFO L93 Difference]: Finished difference Result 846 states and 1157 transitions. [2021-12-14 14:06:40,613 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 43 states. [2021-12-14 14:06:40,613 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 26 states have (on average 4.3076923076923075) internal successors, (112), 26 states have internal predecessors, (112), 23 states have call successors, (25), 13 states have call predecessors, (25), 12 states have return successors, (24), 22 states have call predecessors, (24), 22 states have call successors, (24) Word has length 99 [2021-12-14 14:06:40,613 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 14:06:40,617 INFO L225 Difference]: With dead ends: 846 [2021-12-14 14:06:40,617 INFO L226 Difference]: Without dead ends: 841 [2021-12-14 14:06:40,618 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 214 GetRequests, 172 SyntacticMatches, 0 SemanticMatches, 42 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 229 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=670, Invalid=1222, Unknown=0, NotChecked=0, Total=1892 [2021-12-14 14:06:40,618 INFO L933 BasicCegarLoop]: 89 mSDtfsCounter, 627 mSDsluCounter, 340 mSDsCounter, 0 mSdLazyCounter, 358 mSolverCounterSat, 390 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 627 SdHoareTripleChecker+Valid, 429 SdHoareTripleChecker+Invalid, 748 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 390 IncrementalHoareTripleChecker+Valid, 358 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2021-12-14 14:06:40,618 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [627 Valid, 429 Invalid, 748 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [390 Valid, 358 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2021-12-14 14:06:40,619 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 841 states. [2021-12-14 14:06:40,667 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 841 to 826. [2021-12-14 14:06:40,668 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 826 states, 620 states have (on average 1.2) internal successors, (744), 626 states have internal predecessors, (744), 182 states have call successors, (182), 24 states have call predecessors, (182), 23 states have return successors, (181), 175 states have call predecessors, (181), 181 states have call successors, (181) [2021-12-14 14:06:40,672 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 826 states to 826 states and 1107 transitions. [2021-12-14 14:06:40,672 INFO L78 Accepts]: Start accepts. Automaton has 826 states and 1107 transitions. Word has length 99 [2021-12-14 14:06:40,672 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 14:06:40,673 INFO L470 AbstractCegarLoop]: Abstraction has 826 states and 1107 transitions. [2021-12-14 14:06:40,673 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 26 states have (on average 4.3076923076923075) internal successors, (112), 26 states have internal predecessors, (112), 23 states have call successors, (25), 13 states have call predecessors, (25), 12 states have return successors, (24), 22 states have call predecessors, (24), 22 states have call successors, (24) [2021-12-14 14:06:40,673 INFO L276 IsEmpty]: Start isEmpty. Operand 826 states and 1107 transitions. [2021-12-14 14:06:40,677 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 178 [2021-12-14 14:06:40,677 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 14:06:40,678 INFO L514 BasicCegarLoop]: trace histogram [20, 19, 19, 9, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 5, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 14:06:40,700 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2021-12-14 14:06:40,900 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:06:40,900 INFO L402 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 14:06:40,901 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 14:06:40,901 INFO L85 PathProgramCache]: Analyzing trace with hash 1985812011, now seen corresponding path program 3 times [2021-12-14 14:06:40,901 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 14:06:40,901 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1159486075] [2021-12-14 14:06:40,901 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:06:40,901 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 14:06:40,920 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-14 14:06:40,920 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1482283342] [2021-12-14 14:06:40,920 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-12-14 14:06:40,921 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:06:40,921 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 14:06:40,925 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-14 14:06:40,940 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2021-12-14 14:06:40,978 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2021-12-14 14:06:40,978 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-14 14:06:40,979 INFO L263 TraceCheckSpWp]: Trace formula consists of 144 conjuncts, 4 conjunts are in the unsatisfiable core [2021-12-14 14:06:40,981 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 14:06:41,196 INFO L134 CoverageAnalysis]: Checked inductivity of 984 backedges. 255 proven. 0 refuted. 0 times theorem prover too weak. 729 trivial. 0 not checked. [2021-12-14 14:06:41,196 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-14 14:06:41,197 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 14:06:41,197 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1159486075] [2021-12-14 14:06:41,197 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-14 14:06:41,197 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1482283342] [2021-12-14 14:06:41,197 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1482283342] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-14 14:06:41,197 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-14 14:06:41,198 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-12-14 14:06:41,198 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [967954506] [2021-12-14 14:06:41,198 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-14 14:06:41,199 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-12-14 14:06:41,199 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 14:06:41,199 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-12-14 14:06:41,199 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-12-14 14:06:41,200 INFO L87 Difference]: Start difference. First operand 826 states and 1107 transitions. Second operand has 5 states, 5 states have (on average 7.6) internal successors, (38), 5 states have internal predecessors, (38), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2021-12-14 14:06:41,273 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 14:06:41,273 INFO L93 Difference]: Finished difference Result 1124 states and 1528 transitions. [2021-12-14 14:06:41,273 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-12-14 14:06:41,274 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 7.6) internal successors, (38), 5 states have internal predecessors, (38), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 177 [2021-12-14 14:06:41,274 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 14:06:41,278 INFO L225 Difference]: With dead ends: 1124 [2021-12-14 14:06:41,278 INFO L226 Difference]: Without dead ends: 905 [2021-12-14 14:06:41,280 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 178 GetRequests, 173 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2021-12-14 14:06:41,281 INFO L933 BasicCegarLoop]: 44 mSDtfsCounter, 15 mSDsluCounter, 105 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 149 SdHoareTripleChecker+Invalid, 44 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-14 14:06:41,281 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [15 Valid, 149 Invalid, 44 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-14 14:06:41,282 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 905 states. [2021-12-14 14:06:41,337 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 905 to 838. [2021-12-14 14:06:41,338 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 838 states, 631 states have (on average 1.185419968304279) internal successors, (748), 637 states have internal predecessors, (748), 182 states have call successors, (182), 25 states have call predecessors, (182), 24 states have return successors, (181), 175 states have call predecessors, (181), 181 states have call successors, (181) [2021-12-14 14:06:41,342 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 838 states to 838 states and 1111 transitions. [2021-12-14 14:06:41,342 INFO L78 Accepts]: Start accepts. Automaton has 838 states and 1111 transitions. Word has length 177 [2021-12-14 14:06:41,343 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 14:06:41,343 INFO L470 AbstractCegarLoop]: Abstraction has 838 states and 1111 transitions. [2021-12-14 14:06:41,343 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 7.6) internal successors, (38), 5 states have internal predecessors, (38), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2021-12-14 14:06:41,343 INFO L276 IsEmpty]: Start isEmpty. Operand 838 states and 1111 transitions. [2021-12-14 14:06:41,347 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 184 [2021-12-14 14:06:41,347 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 14:06:41,347 INFO L514 BasicCegarLoop]: trace histogram [21, 20, 20, 11, 10, 10, 10, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 14:06:41,371 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2021-12-14 14:06:41,571 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2021-12-14 14:06:41,571 INFO L402 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 14:06:41,572 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 14:06:41,572 INFO L85 PathProgramCache]: Analyzing trace with hash 1801897766, now seen corresponding path program 4 times [2021-12-14 14:06:41,572 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 14:06:41,572 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [975635501] [2021-12-14 14:06:41,572 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:06:41,572 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 14:06:41,584 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-14 14:06:41,584 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1090562615] [2021-12-14 14:06:41,584 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2021-12-14 14:06:41,584 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:06:41,585 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 14:06:41,585 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-14 14:06:41,587 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2021-12-14 14:06:41,652 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2021-12-14 14:06:41,652 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-14 14:06:41,654 INFO L263 TraceCheckSpWp]: Trace formula consists of 355 conjuncts, 2 conjunts are in the unsatisfiable core [2021-12-14 14:06:41,656 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 14:06:41,868 INFO L134 CoverageAnalysis]: Checked inductivity of 1104 backedges. 612 proven. 0 refuted. 0 times theorem prover too weak. 492 trivial. 0 not checked. [2021-12-14 14:06:41,869 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-14 14:06:41,869 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 14:06:41,869 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [975635501] [2021-12-14 14:06:41,869 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-14 14:06:41,869 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1090562615] [2021-12-14 14:06:41,869 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1090562615] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-14 14:06:41,869 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-14 14:06:41,869 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2021-12-14 14:06:41,869 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1119875680] [2021-12-14 14:06:41,869 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-14 14:06:41,870 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2021-12-14 14:06:41,870 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 14:06:41,870 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2021-12-14 14:06:41,870 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-12-14 14:06:41,870 INFO L87 Difference]: Start difference. First operand 838 states and 1111 transitions. Second operand has 3 states, 3 states have (on average 16.0) internal successors, (48), 3 states have internal predecessors, (48), 3 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2021-12-14 14:06:41,945 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 14:06:41,945 INFO L93 Difference]: Finished difference Result 1423 states and 1887 transitions. [2021-12-14 14:06:41,946 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2021-12-14 14:06:41,946 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 16.0) internal successors, (48), 3 states have internal predecessors, (48), 3 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) Word has length 183 [2021-12-14 14:06:41,946 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 14:06:41,950 INFO L225 Difference]: With dead ends: 1423 [2021-12-14 14:06:41,950 INFO L226 Difference]: Without dead ends: 899 [2021-12-14 14:06:41,951 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 182 GetRequests, 181 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-12-14 14:06:41,951 INFO L933 BasicCegarLoop]: 48 mSDtfsCounter, 3 mSDsluCounter, 32 mSDsCounter, 0 mSdLazyCounter, 10 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 80 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 10 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-14 14:06:41,952 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [3 Valid, 80 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 10 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-14 14:06:41,953 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 899 states. [2021-12-14 14:06:41,999 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 899 to 830. [2021-12-14 14:06:42,000 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 830 states, 626 states have (on average 1.1789137380191694) internal successors, (738), 634 states have internal predecessors, (738), 179 states have call successors, (179), 25 states have call predecessors, (179), 24 states have return successors, (178), 170 states have call predecessors, (178), 178 states have call successors, (178) [2021-12-14 14:06:42,003 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 830 states to 830 states and 1095 transitions. [2021-12-14 14:06:42,004 INFO L78 Accepts]: Start accepts. Automaton has 830 states and 1095 transitions. Word has length 183 [2021-12-14 14:06:42,004 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 14:06:42,004 INFO L470 AbstractCegarLoop]: Abstraction has 830 states and 1095 transitions. [2021-12-14 14:06:42,004 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 16.0) internal successors, (48), 3 states have internal predecessors, (48), 3 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2021-12-14 14:06:42,004 INFO L276 IsEmpty]: Start isEmpty. Operand 830 states and 1095 transitions. [2021-12-14 14:06:42,007 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 184 [2021-12-14 14:06:42,008 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 14:06:42,008 INFO L514 BasicCegarLoop]: trace histogram [21, 20, 20, 9, 8, 8, 8, 8, 7, 7, 7, 6, 5, 5, 5, 5, 4, 4, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 14:06:42,030 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2021-12-14 14:06:42,227 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2021-12-14 14:06:42,227 INFO L402 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 14:06:42,228 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 14:06:42,228 INFO L85 PathProgramCache]: Analyzing trace with hash -670817854, now seen corresponding path program 5 times [2021-12-14 14:06:42,228 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 14:06:42,228 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [193598633] [2021-12-14 14:06:42,228 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:06:42,228 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 14:06:42,236 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-14 14:06:42,236 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1934930833] [2021-12-14 14:06:42,236 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2021-12-14 14:06:42,236 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:06:42,236 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 14:06:42,237 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-14 14:06:42,238 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2021-12-14 14:06:42,395 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 14 check-sat command(s) [2021-12-14 14:06:42,396 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-14 14:06:42,397 INFO L263 TraceCheckSpWp]: Trace formula consists of 349 conjuncts, 3 conjunts are in the unsatisfiable core [2021-12-14 14:06:42,399 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 14:06:42,640 INFO L134 CoverageAnalysis]: Checked inductivity of 1080 backedges. 120 proven. 0 refuted. 0 times theorem prover too weak. 960 trivial. 0 not checked. [2021-12-14 14:06:42,640 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-14 14:06:42,640 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 14:06:42,640 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [193598633] [2021-12-14 14:06:42,640 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-14 14:06:42,640 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1934930833] [2021-12-14 14:06:42,640 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1934930833] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-14 14:06:42,640 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-14 14:06:42,640 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2021-12-14 14:06:42,641 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [228297595] [2021-12-14 14:06:42,641 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-14 14:06:42,641 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2021-12-14 14:06:42,641 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 14:06:42,641 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-12-14 14:06:42,641 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2021-12-14 14:06:42,642 INFO L87 Difference]: Start difference. First operand 830 states and 1095 transitions. Second operand has 4 states, 4 states have (on average 9.0) internal successors, (36), 4 states have internal predecessors, (36), 4 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2021-12-14 14:06:42,692 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 14:06:42,692 INFO L93 Difference]: Finished difference Result 883 states and 1153 transitions. [2021-12-14 14:06:42,693 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2021-12-14 14:06:42,693 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 9.0) internal successors, (36), 4 states have internal predecessors, (36), 4 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) Word has length 183 [2021-12-14 14:06:42,693 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 14:06:42,697 INFO L225 Difference]: With dead ends: 883 [2021-12-14 14:06:42,697 INFO L226 Difference]: Without dead ends: 798 [2021-12-14 14:06:42,698 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 182 GetRequests, 180 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2021-12-14 14:06:42,698 INFO L933 BasicCegarLoop]: 51 mSDtfsCounter, 12 mSDsluCounter, 73 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 23 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 22 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-14 14:06:42,698 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 124 Invalid, 23 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-14 14:06:42,699 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 798 states. [2021-12-14 14:06:42,744 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 798 to 777. [2021-12-14 14:06:42,745 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 777 states, 586 states have (on average 1.1706484641638226) internal successors, (686), 593 states have internal predecessors, (686), 166 states have call successors, (166), 25 states have call predecessors, (166), 24 states have return successors, (165), 158 states have call predecessors, (165), 165 states have call successors, (165) [2021-12-14 14:06:42,748 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 777 states to 777 states and 1017 transitions. [2021-12-14 14:06:42,748 INFO L78 Accepts]: Start accepts. Automaton has 777 states and 1017 transitions. Word has length 183 [2021-12-14 14:06:42,749 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 14:06:42,749 INFO L470 AbstractCegarLoop]: Abstraction has 777 states and 1017 transitions. [2021-12-14 14:06:42,749 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 9.0) internal successors, (36), 4 states have internal predecessors, (36), 4 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2021-12-14 14:06:42,749 INFO L276 IsEmpty]: Start isEmpty. Operand 777 states and 1017 transitions. [2021-12-14 14:06:42,752 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 184 [2021-12-14 14:06:42,752 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 14:06:42,752 INFO L514 BasicCegarLoop]: trace histogram [21, 20, 20, 11, 10, 10, 10, 7, 7, 6, 6, 6, 5, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 14:06:42,762 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2021-12-14 14:06:42,957 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2021-12-14 14:06:42,958 INFO L402 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 14:06:42,958 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 14:06:42,958 INFO L85 PathProgramCache]: Analyzing trace with hash -1332064508, now seen corresponding path program 6 times [2021-12-14 14:06:42,958 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 14:06:42,959 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [80465187] [2021-12-14 14:06:42,959 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:06:42,959 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 14:06:42,968 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-14 14:06:42,968 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [694363134] [2021-12-14 14:06:42,968 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2021-12-14 14:06:42,968 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:06:42,968 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 14:06:42,969 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-14 14:06:42,971 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2021-12-14 14:06:44,880 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 12 check-sat command(s) [2021-12-14 14:06:44,880 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-14 14:06:44,883 INFO L263 TraceCheckSpWp]: Trace formula consists of 419 conjuncts, 17 conjunts are in the unsatisfiable core [2021-12-14 14:06:44,886 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 14:06:45,616 INFO L134 CoverageAnalysis]: Checked inductivity of 1108 backedges. 192 proven. 140 refuted. 0 times theorem prover too weak. 776 trivial. 0 not checked. [2021-12-14 14:06:45,616 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 14:06:46,158 INFO L134 CoverageAnalysis]: Checked inductivity of 1108 backedges. 192 proven. 140 refuted. 0 times theorem prover too weak. 776 trivial. 0 not checked. [2021-12-14 14:06:46,160 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 14:06:46,160 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [80465187] [2021-12-14 14:06:46,160 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-14 14:06:46,160 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [694363134] [2021-12-14 14:06:46,160 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [694363134] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-14 14:06:46,161 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-14 14:06:46,161 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 18 [2021-12-14 14:06:46,161 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [43880310] [2021-12-14 14:06:46,161 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-14 14:06:46,162 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2021-12-14 14:06:46,162 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 14:06:46,162 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2021-12-14 14:06:46,163 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=265, Unknown=0, NotChecked=0, Total=306 [2021-12-14 14:06:46,163 INFO L87 Difference]: Start difference. First operand 777 states and 1017 transitions. Second operand has 18 states, 18 states have (on average 6.333333333333333) internal successors, (114), 18 states have internal predecessors, (114), 18 states have call successors, (34), 2 states have call predecessors, (34), 1 states have return successors, (33), 17 states have call predecessors, (33), 17 states have call successors, (33) [2021-12-14 14:06:53,820 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 14:06:53,821 INFO L93 Difference]: Finished difference Result 4123 states and 5725 transitions. [2021-12-14 14:06:53,821 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 72 states. [2021-12-14 14:06:53,821 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 6.333333333333333) internal successors, (114), 18 states have internal predecessors, (114), 18 states have call successors, (34), 2 states have call predecessors, (34), 1 states have return successors, (33), 17 states have call predecessors, (33), 17 states have call successors, (33) Word has length 183 [2021-12-14 14:06:53,822 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 14:06:53,837 INFO L225 Difference]: With dead ends: 4123 [2021-12-14 14:06:53,837 INFO L226 Difference]: Without dead ends: 3828 [2021-12-14 14:06:53,840 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 493 GetRequests, 412 SyntacticMatches, 0 SemanticMatches, 81 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1955 ImplicationChecksByTransitivity, 5.8s TimeCoverageRelationStatistics Valid=1256, Invalid=5549, Unknown=1, NotChecked=0, Total=6806 [2021-12-14 14:06:53,841 INFO L933 BasicCegarLoop]: 403 mSDtfsCounter, 533 mSDsluCounter, 2558 mSDsCounter, 0 mSdLazyCounter, 1660 mSolverCounterSat, 409 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 537 SdHoareTripleChecker+Valid, 2961 SdHoareTripleChecker+Invalid, 2507 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 409 IncrementalHoareTripleChecker+Valid, 1660 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 438 IncrementalHoareTripleChecker+Unchecked, 1.7s IncrementalHoareTripleChecker+Time [2021-12-14 14:06:53,841 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [537 Valid, 2961 Invalid, 2507 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [409 Valid, 1660 Invalid, 0 Unknown, 438 Unchecked, 1.7s Time] [2021-12-14 14:06:53,844 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3828 states. [2021-12-14 14:06:54,084 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3828 to 2443. [2021-12-14 14:06:54,087 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2443 states, 1852 states have (on average 1.2300215982721383) internal successors, (2278), 1887 states have internal predecessors, (2278), 566 states have call successors, (566), 25 states have call predecessors, (566), 24 states have return successors, (565), 530 states have call predecessors, (565), 565 states have call successors, (565) [2021-12-14 14:06:54,096 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2443 states to 2443 states and 3409 transitions. [2021-12-14 14:06:54,096 INFO L78 Accepts]: Start accepts. Automaton has 2443 states and 3409 transitions. Word has length 183 [2021-12-14 14:06:54,097 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 14:06:54,097 INFO L470 AbstractCegarLoop]: Abstraction has 2443 states and 3409 transitions. [2021-12-14 14:06:54,097 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 6.333333333333333) internal successors, (114), 18 states have internal predecessors, (114), 18 states have call successors, (34), 2 states have call predecessors, (34), 1 states have return successors, (33), 17 states have call predecessors, (33), 17 states have call successors, (33) [2021-12-14 14:06:54,097 INFO L276 IsEmpty]: Start isEmpty. Operand 2443 states and 3409 transitions. [2021-12-14 14:06:54,105 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 184 [2021-12-14 14:06:54,105 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 14:06:54,105 INFO L514 BasicCegarLoop]: trace histogram [21, 20, 20, 9, 9, 8, 8, 8, 8, 8, 8, 5, 5, 5, 4, 4, 4, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 14:06:54,117 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2021-12-14 14:06:54,312 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2021-12-14 14:06:54,312 INFO L402 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 14:06:54,313 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 14:06:54,313 INFO L85 PathProgramCache]: Analyzing trace with hash -601397856, now seen corresponding path program 7 times [2021-12-14 14:06:54,313 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 14:06:54,313 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1124477643] [2021-12-14 14:06:54,313 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:06:54,313 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 14:06:54,321 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-14 14:06:54,333 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1599221178] [2021-12-14 14:06:54,334 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2021-12-14 14:06:54,334 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:06:54,334 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 14:06:54,335 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-14 14:06:54,338 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2021-12-14 14:06:54,416 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:06:54,418 INFO L263 TraceCheckSpWp]: Trace formula consists of 419 conjuncts, 13 conjunts are in the unsatisfiable core [2021-12-14 14:06:54,420 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 14:06:54,852 INFO L134 CoverageAnalysis]: Checked inductivity of 1092 backedges. 516 proven. 84 refuted. 0 times theorem prover too weak. 492 trivial. 0 not checked. [2021-12-14 14:06:54,852 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 14:06:55,196 INFO L134 CoverageAnalysis]: Checked inductivity of 1092 backedges. 226 proven. 84 refuted. 0 times theorem prover too weak. 782 trivial. 0 not checked. [2021-12-14 14:06:55,196 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 14:06:55,196 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1124477643] [2021-12-14 14:06:55,196 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-14 14:06:55,196 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1599221178] [2021-12-14 14:06:55,197 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1599221178] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-14 14:06:55,197 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-14 14:06:55,197 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2021-12-14 14:06:55,197 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1222823182] [2021-12-14 14:06:55,197 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-14 14:06:55,197 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2021-12-14 14:06:55,197 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 14:06:55,198 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2021-12-14 14:06:55,198 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=147, Unknown=0, NotChecked=0, Total=182 [2021-12-14 14:06:55,198 INFO L87 Difference]: Start difference. First operand 2443 states and 3409 transitions. Second operand has 14 states, 14 states have (on average 7.785714285714286) internal successors, (109), 14 states have internal predecessors, (109), 14 states have call successors, (36), 2 states have call predecessors, (36), 2 states have return successors, (35), 14 states have call predecessors, (35), 14 states have call successors, (35) [2021-12-14 14:06:56,359 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 14:06:56,359 INFO L93 Difference]: Finished difference Result 5571 states and 7891 transitions. [2021-12-14 14:06:56,359 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2021-12-14 14:06:56,359 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 7.785714285714286) internal successors, (109), 14 states have internal predecessors, (109), 14 states have call successors, (36), 2 states have call predecessors, (36), 2 states have return successors, (35), 14 states have call predecessors, (35), 14 states have call successors, (35) Word has length 183 [2021-12-14 14:06:56,360 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 14:06:56,383 INFO L225 Difference]: With dead ends: 5571 [2021-12-14 14:06:56,384 INFO L226 Difference]: Without dead ends: 4349 [2021-12-14 14:06:56,387 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 414 GetRequests, 377 SyntacticMatches, 0 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 262 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=385, Invalid=1097, Unknown=0, NotChecked=0, Total=1482 [2021-12-14 14:06:56,388 INFO L933 BasicCegarLoop]: 181 mSDtfsCounter, 179 mSDsluCounter, 922 mSDsCounter, 0 mSdLazyCounter, 558 mSolverCounterSat, 129 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 184 SdHoareTripleChecker+Valid, 1103 SdHoareTripleChecker+Invalid, 687 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 129 IncrementalHoareTripleChecker+Valid, 558 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2021-12-14 14:06:56,388 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [184 Valid, 1103 Invalid, 687 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [129 Valid, 558 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2021-12-14 14:06:56,391 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 4349 states. [2021-12-14 14:06:56,749 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 4349 to 3548. [2021-12-14 14:06:56,756 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3548 states, 2684 states have (on average 1.222429210134128) internal successors, (3281), 2738 states have internal predecessors, (3281), 839 states have call successors, (839), 25 states have call predecessors, (839), 24 states have return successors, (838), 784 states have call predecessors, (838), 838 states have call successors, (838) [2021-12-14 14:06:56,765 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3548 states to 3548 states and 4958 transitions. [2021-12-14 14:06:56,766 INFO L78 Accepts]: Start accepts. Automaton has 3548 states and 4958 transitions. Word has length 183 [2021-12-14 14:06:56,766 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 14:06:56,767 INFO L470 AbstractCegarLoop]: Abstraction has 3548 states and 4958 transitions. [2021-12-14 14:06:56,767 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 7.785714285714286) internal successors, (109), 14 states have internal predecessors, (109), 14 states have call successors, (36), 2 states have call predecessors, (36), 2 states have return successors, (35), 14 states have call predecessors, (35), 14 states have call successors, (35) [2021-12-14 14:06:56,767 INFO L276 IsEmpty]: Start isEmpty. Operand 3548 states and 4958 transitions. [2021-12-14 14:06:56,779 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 184 [2021-12-14 14:06:56,779 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 14:06:56,779 INFO L514 BasicCegarLoop]: trace histogram [21, 20, 20, 11, 10, 10, 10, 7, 7, 6, 6, 6, 5, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 14:06:56,807 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Forceful destruction successful, exit code 0 [2021-12-14 14:06:56,995 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,20 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:06:56,995 INFO L402 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 14:06:56,996 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 14:06:56,996 INFO L85 PathProgramCache]: Analyzing trace with hash 144972548, now seen corresponding path program 8 times [2021-12-14 14:06:56,996 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 14:06:56,996 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [246988881] [2021-12-14 14:06:56,996 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:06:56,996 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 14:06:57,003 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-14 14:06:57,006 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2125758085] [2021-12-14 14:06:57,007 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2021-12-14 14:06:57,007 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:06:57,008 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 14:06:57,009 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-14 14:06:57,012 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2021-12-14 14:06:57,085 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-12-14 14:06:57,085 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-14 14:06:57,087 INFO L263 TraceCheckSpWp]: Trace formula consists of 419 conjuncts, 16 conjunts are in the unsatisfiable core [2021-12-14 14:06:57,090 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 14:06:57,463 INFO L134 CoverageAnalysis]: Checked inductivity of 1108 backedges. 80 proven. 252 refuted. 0 times theorem prover too weak. 776 trivial. 0 not checked. [2021-12-14 14:06:57,463 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 14:06:57,905 INFO L134 CoverageAnalysis]: Checked inductivity of 1108 backedges. 80 proven. 252 refuted. 0 times theorem prover too weak. 776 trivial. 0 not checked. [2021-12-14 14:06:57,905 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 14:06:57,906 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [246988881] [2021-12-14 14:06:57,906 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-14 14:06:57,906 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2125758085] [2021-12-14 14:06:57,906 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2125758085] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-14 14:06:57,906 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-14 14:06:57,906 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 20 [2021-12-14 14:06:57,906 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1702750290] [2021-12-14 14:06:57,907 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-14 14:06:57,908 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2021-12-14 14:06:57,908 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 14:06:57,908 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2021-12-14 14:06:57,908 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=330, Unknown=0, NotChecked=0, Total=380 [2021-12-14 14:06:57,909 INFO L87 Difference]: Start difference. First operand 3548 states and 4958 transitions. Second operand has 20 states, 20 states have (on average 6.25) internal successors, (125), 20 states have internal predecessors, (125), 20 states have call successors, (37), 2 states have call predecessors, (37), 1 states have return successors, (36), 19 states have call predecessors, (36), 19 states have call successors, (36) [2021-12-14 14:07:01,826 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 14:07:01,827 INFO L93 Difference]: Finished difference Result 9328 states and 13208 transitions. [2021-12-14 14:07:01,827 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 86 states. [2021-12-14 14:07:01,827 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 6.25) internal successors, (125), 20 states have internal predecessors, (125), 20 states have call successors, (37), 2 states have call predecessors, (37), 1 states have return successors, (36), 19 states have call predecessors, (36), 19 states have call successors, (36) Word has length 183 [2021-12-14 14:07:01,828 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 14:07:01,859 INFO L225 Difference]: With dead ends: 9328 [2021-12-14 14:07:01,859 INFO L226 Difference]: Without dead ends: 8358 [2021-12-14 14:07:01,866 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 440 GetRequests, 346 SyntacticMatches, 0 SemanticMatches, 94 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2742 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=1198, Invalid=7922, Unknown=0, NotChecked=0, Total=9120 [2021-12-14 14:07:01,866 INFO L933 BasicCegarLoop]: 467 mSDtfsCounter, 424 mSDsluCounter, 3424 mSDsCounter, 0 mSdLazyCounter, 2563 mSolverCounterSat, 339 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 430 SdHoareTripleChecker+Valid, 3891 SdHoareTripleChecker+Invalid, 2902 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 339 IncrementalHoareTripleChecker+Valid, 2563 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.5s IncrementalHoareTripleChecker+Time [2021-12-14 14:07:01,866 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [430 Valid, 3891 Invalid, 2902 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [339 Valid, 2563 Invalid, 0 Unknown, 0 Unchecked, 1.5s Time] [2021-12-14 14:07:01,872 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 8358 states. [2021-12-14 14:07:02,601 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 8358 to 6524. [2021-12-14 14:07:02,624 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6524 states, 4924 states have (on average 1.2303005686433794) internal successors, (6058), 5046 states have internal predecessors, (6058), 1575 states have call successors, (1575), 25 states have call predecessors, (1575), 24 states have return successors, (1574), 1452 states have call predecessors, (1574), 1574 states have call successors, (1574) [2021-12-14 14:07:02,638 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6524 states to 6524 states and 9207 transitions. [2021-12-14 14:07:02,638 INFO L78 Accepts]: Start accepts. Automaton has 6524 states and 9207 transitions. Word has length 183 [2021-12-14 14:07:02,639 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 14:07:02,639 INFO L470 AbstractCegarLoop]: Abstraction has 6524 states and 9207 transitions. [2021-12-14 14:07:02,640 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 6.25) internal successors, (125), 20 states have internal predecessors, (125), 20 states have call successors, (37), 2 states have call predecessors, (37), 1 states have return successors, (36), 19 states have call predecessors, (36), 19 states have call successors, (36) [2021-12-14 14:07:02,640 INFO L276 IsEmpty]: Start isEmpty. Operand 6524 states and 9207 transitions. [2021-12-14 14:07:02,661 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 184 [2021-12-14 14:07:02,662 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 14:07:02,662 INFO L514 BasicCegarLoop]: trace histogram [21, 20, 20, 11, 10, 10, 10, 7, 7, 6, 6, 6, 5, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 14:07:02,687 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Forceful destruction successful, exit code 0 [2021-12-14 14:07:02,887 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,21 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:07:02,888 INFO L402 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 14:07:02,888 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 14:07:02,888 INFO L85 PathProgramCache]: Analyzing trace with hash 1027204868, now seen corresponding path program 9 times [2021-12-14 14:07:02,888 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 14:07:02,888 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1949606494] [2021-12-14 14:07:02,888 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:07:02,889 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 14:07:02,896 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-14 14:07:02,896 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [612646365] [2021-12-14 14:07:02,896 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-12-14 14:07:02,896 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:07:02,896 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 14:07:02,900 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-14 14:07:02,901 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Waiting until timeout for monitored process [2021-12-14 14:07:03,999 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 12 check-sat command(s) [2021-12-14 14:07:03,999 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-14 14:07:04,002 INFO L263 TraceCheckSpWp]: Trace formula consists of 419 conjuncts, 43 conjunts are in the unsatisfiable core [2021-12-14 14:07:04,004 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 14:07:04,462 INFO L134 CoverageAnalysis]: Checked inductivity of 1108 backedges. 60 proven. 1044 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-12-14 14:07:04,463 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 14:07:05,189 INFO L134 CoverageAnalysis]: Checked inductivity of 1108 backedges. 60 proven. 284 refuted. 0 times theorem prover too weak. 764 trivial. 0 not checked. [2021-12-14 14:07:05,190 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 14:07:05,190 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1949606494] [2021-12-14 14:07:05,190 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-14 14:07:05,190 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [612646365] [2021-12-14 14:07:05,190 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [612646365] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-14 14:07:05,190 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-14 14:07:05,190 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 24] total 46 [2021-12-14 14:07:05,190 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1566443781] [2021-12-14 14:07:05,190 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-14 14:07:05,191 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 46 states [2021-12-14 14:07:05,191 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 14:07:05,191 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 46 interpolants. [2021-12-14 14:07:05,192 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=951, Invalid=1119, Unknown=0, NotChecked=0, Total=2070 [2021-12-14 14:07:05,192 INFO L87 Difference]: Start difference. First operand 6524 states and 9207 transitions. Second operand has 46 states, 46 states have (on average 4.478260869565218) internal successors, (206), 46 states have internal predecessors, (206), 43 states have call successors, (45), 23 states have call predecessors, (45), 22 states have return successors, (44), 42 states have call predecessors, (44), 42 states have call successors, (44) [2021-12-14 14:07:09,139 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 14:07:09,140 INFO L93 Difference]: Finished difference Result 32301 states and 50042 transitions. [2021-12-14 14:07:09,140 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 85 states. [2021-12-14 14:07:09,140 INFO L78 Accepts]: Start accepts. Automaton has has 46 states, 46 states have (on average 4.478260869565218) internal successors, (206), 46 states have internal predecessors, (206), 43 states have call successors, (45), 23 states have call predecessors, (45), 22 states have return successors, (44), 42 states have call predecessors, (44), 42 states have call successors, (44) Word has length 183 [2021-12-14 14:07:09,141 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 14:07:09,236 INFO L225 Difference]: With dead ends: 32301 [2021-12-14 14:07:09,237 INFO L226 Difference]: Without dead ends: 32106 [2021-12-14 14:07:09,250 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 404 GetRequests, 320 SyntacticMatches, 0 SemanticMatches, 84 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1031 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=2691, Invalid=4619, Unknown=0, NotChecked=0, Total=7310 [2021-12-14 14:07:09,250 INFO L933 BasicCegarLoop]: 149 mSDtfsCounter, 1609 mSDsluCounter, 685 mSDsCounter, 0 mSdLazyCounter, 790 mSolverCounterSat, 1156 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1609 SdHoareTripleChecker+Valid, 834 SdHoareTripleChecker+Invalid, 1946 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1156 IncrementalHoareTripleChecker+Valid, 790 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2021-12-14 14:07:09,251 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [1609 Valid, 834 Invalid, 1946 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1156 Valid, 790 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2021-12-14 14:07:09,273 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32106 states. [2021-12-14 14:07:12,015 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32106 to 31571. [2021-12-14 14:07:12,046 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31571 states, 23756 states have (on average 1.2964724701128136) internal successors, (30799), 23919 states have internal predecessors, (30799), 7770 states have call successors, (7770), 45 states have call predecessors, (7770), 44 states have return successors, (7769), 7606 states have call predecessors, (7769), 7769 states have call successors, (7769) [2021-12-14 14:07:12,128 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31571 states to 31571 states and 46338 transitions. [2021-12-14 14:07:12,128 INFO L78 Accepts]: Start accepts. Automaton has 31571 states and 46338 transitions. Word has length 183 [2021-12-14 14:07:12,129 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 14:07:12,129 INFO L470 AbstractCegarLoop]: Abstraction has 31571 states and 46338 transitions. [2021-12-14 14:07:12,129 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 46 states, 46 states have (on average 4.478260869565218) internal successors, (206), 46 states have internal predecessors, (206), 43 states have call successors, (45), 23 states have call predecessors, (45), 22 states have return successors, (44), 42 states have call predecessors, (44), 42 states have call successors, (44) [2021-12-14 14:07:12,130 INFO L276 IsEmpty]: Start isEmpty. Operand 31571 states and 46338 transitions. [2021-12-14 14:07:12,150 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 190 [2021-12-14 14:07:12,150 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 14:07:12,150 INFO L514 BasicCegarLoop]: trace histogram [22, 21, 21, 10, 10, 10, 10, 8, 7, 7, 7, 6, 5, 4, 4, 4, 4, 4, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 14:07:12,159 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Forceful destruction successful, exit code 0 [2021-12-14 14:07:12,356 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20,22 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:07:12,356 INFO L402 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 14:07:12,357 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 14:07:12,357 INFO L85 PathProgramCache]: Analyzing trace with hash -1981009717, now seen corresponding path program 2 times [2021-12-14 14:07:12,357 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 14:07:12,357 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [841158850] [2021-12-14 14:07:12,357 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:07:12,358 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 14:07:12,379 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-14 14:07:12,380 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [133834149] [2021-12-14 14:07:12,380 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2021-12-14 14:07:12,380 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:07:12,380 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 14:07:12,381 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-14 14:07:12,382 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Waiting until timeout for monitored process [2021-12-14 14:07:12,453 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-12-14 14:07:12,453 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-14 14:07:12,456 INFO L263 TraceCheckSpWp]: Trace formula consists of 429 conjuncts, 45 conjunts are in the unsatisfiable core [2021-12-14 14:07:12,458 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 14:07:13,026 INFO L134 CoverageAnalysis]: Checked inductivity of 1196 backedges. 50 proven. 1142 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-12-14 14:07:13,026 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 14:07:13,898 INFO L134 CoverageAnalysis]: Checked inductivity of 1196 backedges. 50 proven. 302 refuted. 0 times theorem prover too weak. 844 trivial. 0 not checked. [2021-12-14 14:07:13,898 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 14:07:13,898 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [841158850] [2021-12-14 14:07:13,898 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-14 14:07:13,899 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [133834149] [2021-12-14 14:07:13,899 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [133834149] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-14 14:07:13,899 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-14 14:07:13,899 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 25] total 48 [2021-12-14 14:07:13,899 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [498647094] [2021-12-14 14:07:13,899 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-14 14:07:13,899 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 48 states [2021-12-14 14:07:13,899 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 14:07:13,900 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 48 interpolants. [2021-12-14 14:07:13,901 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1040, Invalid=1216, Unknown=0, NotChecked=0, Total=2256 [2021-12-14 14:07:13,901 INFO L87 Difference]: Start difference. First operand 31571 states and 46338 transitions. Second operand has 48 states, 48 states have (on average 4.4375) internal successors, (213), 48 states have internal predecessors, (213), 45 states have call successors, (47), 24 states have call predecessors, (47), 23 states have return successors, (46), 44 states have call predecessors, (46), 44 states have call successors, (46) [2021-12-14 14:07:17,419 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 14:07:17,419 INFO L93 Difference]: Finished difference Result 45885 states and 68215 transitions. [2021-12-14 14:07:17,423 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 88 states. [2021-12-14 14:07:17,423 INFO L78 Accepts]: Start accepts. Automaton has has 48 states, 48 states have (on average 4.4375) internal successors, (213), 48 states have internal predecessors, (213), 45 states have call successors, (47), 24 states have call predecessors, (47), 23 states have return successors, (46), 44 states have call predecessors, (46), 44 states have call successors, (46) Word has length 189 [2021-12-14 14:07:17,424 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 14:07:17,484 INFO L225 Difference]: With dead ends: 45885 [2021-12-14 14:07:17,484 INFO L226 Difference]: Without dead ends: 21024 [2021-12-14 14:07:17,548 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 417 GetRequests, 330 SyntacticMatches, 0 SemanticMatches, 87 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1094 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=2864, Invalid=4968, Unknown=0, NotChecked=0, Total=7832 [2021-12-14 14:07:17,549 INFO L933 BasicCegarLoop]: 155 mSDtfsCounter, 1669 mSDsluCounter, 830 mSDsCounter, 0 mSdLazyCounter, 750 mSolverCounterSat, 1047 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1669 SdHoareTripleChecker+Valid, 985 SdHoareTripleChecker+Invalid, 1797 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1047 IncrementalHoareTripleChecker+Valid, 750 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2021-12-14 14:07:17,549 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [1669 Valid, 985 Invalid, 1797 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1047 Valid, 750 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2021-12-14 14:07:17,566 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21024 states. [2021-12-14 14:07:19,155 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21024 to 19808. [2021-12-14 14:07:19,173 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 19808 states, 14876 states have (on average 1.217666039257865) internal successors, (18114), 14948 states have internal predecessors, (18114), 4885 states have call successors, (4885), 47 states have call predecessors, (4885), 46 states have return successors, (4884), 4812 states have call predecessors, (4884), 4884 states have call successors, (4884) [2021-12-14 14:07:19,216 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19808 states to 19808 states and 27883 transitions. [2021-12-14 14:07:19,220 INFO L78 Accepts]: Start accepts. Automaton has 19808 states and 27883 transitions. Word has length 189 [2021-12-14 14:07:19,221 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 14:07:19,221 INFO L470 AbstractCegarLoop]: Abstraction has 19808 states and 27883 transitions. [2021-12-14 14:07:19,221 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 48 states, 48 states have (on average 4.4375) internal successors, (213), 48 states have internal predecessors, (213), 45 states have call successors, (47), 24 states have call predecessors, (47), 23 states have return successors, (46), 44 states have call predecessors, (46), 44 states have call successors, (46) [2021-12-14 14:07:19,221 INFO L276 IsEmpty]: Start isEmpty. Operand 19808 states and 27883 transitions. [2021-12-14 14:07:19,240 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 196 [2021-12-14 14:07:19,240 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 14:07:19,241 INFO L514 BasicCegarLoop]: trace histogram [23, 22, 22, 10, 10, 10, 10, 8, 8, 8, 8, 6, 5, 4, 4, 4, 4, 4, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 14:07:19,263 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Forceful destruction successful, exit code 0 [2021-12-14 14:07:19,463 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable21,23 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:07:19,463 INFO L402 AbstractCegarLoop]: === Iteration 23 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 14:07:19,464 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 14:07:19,464 INFO L85 PathProgramCache]: Analyzing trace with hash -1075935086, now seen corresponding path program 2 times [2021-12-14 14:07:19,464 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 14:07:19,464 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [255211030] [2021-12-14 14:07:19,464 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:07:19,464 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 14:07:19,470 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-14 14:07:19,470 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1870163839] [2021-12-14 14:07:19,471 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2021-12-14 14:07:19,471 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:07:19,471 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 14:07:19,474 INFO L229 MonitoredProcess]: Starting monitored process 24 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-14 14:07:19,475 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (24)] Waiting until timeout for monitored process [2021-12-14 14:07:19,550 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-12-14 14:07:19,550 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-14 14:07:19,552 INFO L263 TraceCheckSpWp]: Trace formula consists of 439 conjuncts, 47 conjunts are in the unsatisfiable core [2021-12-14 14:07:19,555 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 14:07:20,110 INFO L134 CoverageAnalysis]: Checked inductivity of 1296 backedges. 44 proven. 1248 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-12-14 14:07:20,110 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 14:07:20,917 INFO L134 CoverageAnalysis]: Checked inductivity of 1296 backedges. 44 proven. 324 refuted. 0 times theorem prover too weak. 928 trivial. 0 not checked. [2021-12-14 14:07:20,917 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 14:07:20,917 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [255211030] [2021-12-14 14:07:20,917 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-14 14:07:20,917 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1870163839] [2021-12-14 14:07:20,917 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1870163839] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-14 14:07:20,917 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-14 14:07:20,917 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 26] total 50 [2021-12-14 14:07:20,917 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [546409405] [2021-12-14 14:07:20,918 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-14 14:07:20,918 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 50 states [2021-12-14 14:07:20,918 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 14:07:20,919 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 50 interpolants. [2021-12-14 14:07:20,919 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1133, Invalid=1317, Unknown=0, NotChecked=0, Total=2450 [2021-12-14 14:07:20,920 INFO L87 Difference]: Start difference. First operand 19808 states and 27883 transitions. Second operand has 50 states, 50 states have (on average 4.4) internal successors, (220), 50 states have internal predecessors, (220), 47 states have call successors, (49), 25 states have call predecessors, (49), 24 states have return successors, (48), 46 states have call predecessors, (48), 46 states have call successors, (48) [2021-12-14 14:07:24,400 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 14:07:24,400 INFO L93 Difference]: Finished difference Result 21460 states and 30403 transitions. [2021-12-14 14:07:24,401 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 91 states. [2021-12-14 14:07:24,401 INFO L78 Accepts]: Start accepts. Automaton has has 50 states, 50 states have (on average 4.4) internal successors, (220), 50 states have internal predecessors, (220), 47 states have call successors, (49), 25 states have call predecessors, (49), 24 states have return successors, (48), 46 states have call predecessors, (48), 46 states have call successors, (48) Word has length 195 [2021-12-14 14:07:24,401 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 14:07:24,454 INFO L225 Difference]: With dead ends: 21460 [2021-12-14 14:07:24,454 INFO L226 Difference]: Without dead ends: 21313 [2021-12-14 14:07:24,466 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 430 GetRequests, 340 SyntacticMatches, 0 SemanticMatches, 90 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1159 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=3046, Invalid=5326, Unknown=0, NotChecked=0, Total=8372 [2021-12-14 14:07:24,467 INFO L933 BasicCegarLoop]: 161 mSDtfsCounter, 1405 mSDsluCounter, 813 mSDsCounter, 0 mSdLazyCounter, 719 mSolverCounterSat, 1106 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1405 SdHoareTripleChecker+Valid, 974 SdHoareTripleChecker+Invalid, 1825 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1106 IncrementalHoareTripleChecker+Valid, 719 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2021-12-14 14:07:24,467 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [1405 Valid, 974 Invalid, 1825 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1106 Valid, 719 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2021-12-14 14:07:24,482 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21313 states.