java -Xss1g -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/large_const.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 15:10:20,760 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 15:10:20,762 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 15:10:20,776 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 15:10:20,777 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 15:10:20,778 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 15:10:20,779 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 15:10:20,782 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 15:10:20,784 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 15:10:20,784 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 15:10:20,786 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 15:10:20,787 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 15:10:20,787 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 15:10:20,788 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 15:10:20,791 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 15:10:20,792 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 15:10:20,801 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 15:10:20,803 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 15:10:20,804 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 15:10:20,805 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 15:10:20,809 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 15:10:20,811 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 15:10:20,811 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 15:10:20,811 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 15:10:20,815 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 15:10:20,816 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 15:10:20,816 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 15:10:20,817 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 15:10:20,822 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 15:10:20,822 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 15:10:20,823 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 15:10:20,823 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 15:10:20,824 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 15:10:20,824 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 15:10:20,826 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 15:10:20,826 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf [2018-06-22 15:10:20,848 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 15:10:20,848 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 15:10:20,849 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 15:10:20,849 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 15:10:20,850 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 15:10:20,850 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 15:10:20,850 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 15:10:20,850 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 15:10:20,850 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 15:10:20,851 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 15:10:20,851 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 15:10:20,851 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 15:10:20,851 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 15:10:20,851 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 15:10:20,851 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 15:10:20,852 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 15:10:20,854 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 15:10:20,854 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 15:10:20,855 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 15:10:20,856 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 15:10:20,856 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 15:10:20,909 INFO ]: Repository-Root is: /tmp [2018-06-22 15:10:20,924 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 15:10:20,929 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 15:10:20,930 INFO ]: Initializing SmtParser... [2018-06-22 15:10:20,930 INFO ]: SmtParser initialized [2018-06-22 15:10:20,931 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/large_const.c.smt2 [2018-06-22 15:10:20,932 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-22 15:10:21,023 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/large_const.c.smt2 unknown [2018-06-22 15:10:21,375 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/large_const.c.smt2 [2018-06-22 15:10:21,380 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 15:10:21,386 INFO ]: Walking toolchain with 4 elements. [2018-06-22 15:10:21,386 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 15:10:21,386 INFO ]: Initializing ChcToBoogie... [2018-06-22 15:10:21,386 INFO ]: ChcToBoogie initialized [2018-06-22 15:10:21,389 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:10:21" (1/1) ... [2018-06-22 15:10:21,439 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:10:21 Unit [2018-06-22 15:10:21,439 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 15:10:21,440 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 15:10:21,440 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 15:10:21,440 INFO ]: Boogie Preprocessor initialized [2018-06-22 15:10:21,459 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:10:21" (1/1) ... [2018-06-22 15:10:21,459 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:10:21" (1/1) ... [2018-06-22 15:10:21,479 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:10:21" (1/1) ... [2018-06-22 15:10:21,479 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:10:21" (1/1) ... [2018-06-22 15:10:21,485 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:10:21" (1/1) ... [2018-06-22 15:10:21,496 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:10:21" (1/1) ... [2018-06-22 15:10:21,498 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:10:21" (1/1) ... [2018-06-22 15:10:21,500 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 15:10:21,501 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 15:10:21,501 INFO ]: Initializing RCFGBuilder... [2018-06-22 15:10:21,501 INFO ]: RCFGBuilder initialized [2018-06-22 15:10:21,501 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:10:21" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 15:10:21,534 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 15:10:21,534 INFO ]: Found specification of procedure False [2018-06-22 15:10:21,534 INFO ]: Found implementation of procedure False [2018-06-22 15:10:21,534 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 15:10:21,534 INFO ]: Found specification of procedure state [2018-06-22 15:10:21,534 INFO ]: Found implementation of procedure state [2018-06-22 15:10:21,534 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 15:10:21,534 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 15:10:21,534 INFO ]: Found implementation of procedure Ultimate.START [2018-06-22 15:10:21,820 INFO ]: Using library mode [2018-06-22 15:10:21,821 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:10:21 BoogieIcfgContainer [2018-06-22 15:10:21,821 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 15:10:21,822 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 15:10:21,822 INFO ]: Initializing TraceAbstraction... [2018-06-22 15:10:21,825 INFO ]: TraceAbstraction initialized [2018-06-22 15:10:21,825 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:10:21" (1/3) ... [2018-06-22 15:10:21,835 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@23acaaab and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 03:10:21, skipping insertion in model container [2018-06-22 15:10:21,835 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:10:21" (2/3) ... [2018-06-22 15:10:21,835 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@23acaaab and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 03:10:21, skipping insertion in model container [2018-06-22 15:10:21,835 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:10:21" (3/3) ... [2018-06-22 15:10:21,837 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 15:10:21,855 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 15:10:21,863 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 15:10:21,915 INFO ]: Using default assertion order modulation [2018-06-22 15:10:21,915 INFO ]: Interprodecural is true [2018-06-22 15:10:21,915 INFO ]: Hoare is false [2018-06-22 15:10:21,915 INFO ]: Compute interpolants for FPandBP [2018-06-22 15:10:21,915 INFO ]: Backedges is TWOTRACK [2018-06-22 15:10:21,915 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 15:10:21,916 INFO ]: Difference is false [2018-06-22 15:10:21,916 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 15:10:21,916 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 15:10:21,928 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 15:10:21,938 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 15:10:21,938 INFO ]: Found error trace [2018-06-22 15:10:21,938 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:10:21,938 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:10:21,945 INFO ]: Analyzing trace with hash -683425083, now seen corresponding path program 1 times [2018-06-22 15:10:21,946 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:10:21,946 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:10:21,979 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:10:21,979 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:10:21,979 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:10:22,011 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:10:22,116 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 15:10:22,120 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 15:10:22,120 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 15:10:22,122 INFO ]: Interpolant automaton has 4 states [2018-06-22 15:10:22,134 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 15:10:22,134 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 15:10:22,136 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 15:10:22,237 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:10:22,237 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 15:10:22,237 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 15:10:22,238 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 15:10:22,239 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:10:22,251 INFO ]: With dead ends: 13 [2018-06-22 15:10:22,251 INFO ]: Without dead ends: 13 [2018-06-22 15:10:22,253 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 15:10:22,265 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 15:10:22,285 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 15:10:22,286 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 15:10:22,286 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 15:10:22,287 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 15:10:22,288 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:10:22,288 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 15:10:22,288 INFO ]: Interpolant automaton has 4 states. [2018-06-22 15:10:22,288 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 15:10:22,289 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 15:10:22,289 INFO ]: Found error trace [2018-06-22 15:10:22,289 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:10:22,289 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:10:22,289 INFO ]: Analyzing trace with hash 204343015, now seen corresponding path program 1 times [2018-06-22 15:10:22,290 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:10:22,290 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:10:22,290 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:10:22,290 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:10:22,291 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:10:22,383 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:10:22,671 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 15:10:22,671 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:10:22,671 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-22 15:10:22,688 INFO ]: Keeping assertion order NOT_INCREMENTALLY Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:10:22,737 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:10:22,744 INFO ]: Computing forward predicates... [2018-06-22 15:10:23,085 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 15:10:23,105 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:10:23,106 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 6 [2018-06-22 15:10:23,106 INFO ]: Interpolant automaton has 6 states [2018-06-22 15:10:23,106 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-22 15:10:23,106 INFO ]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-22 15:10:23,106 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 6 states. [2018-06-22 15:10:23,259 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:10:23,259 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 15:10:23,260 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 15:10:23,260 INFO ]: Start accepts. Automaton has 6 states. Word has length 13 [2018-06-22 15:10:23,260 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:10:23,261 INFO ]: With dead ends: 15 [2018-06-22 15:10:23,261 INFO ]: Without dead ends: 15 [2018-06-22 15:10:23,262 INFO ]: 0 DeclaredPredicates, 18 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-22 15:10:23,262 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 15:10:23,266 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 15:10:23,266 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 15:10:23,267 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 15:10:23,267 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 15:10:23,267 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:10:23,267 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 15:10:23,267 INFO ]: Interpolant automaton has 6 states. [2018-06-22 15:10:23,267 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 15:10:23,267 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 15:10:23,267 INFO ]: Found error trace [2018-06-22 15:10:23,267 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:10:23,268 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:10:23,268 INFO ]: Analyzing trace with hash -1649658231, now seen corresponding path program 2 times [2018-06-22 15:10:23,268 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:10:23,268 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:10:23,269 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:10:23,269 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:10:23,269 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:10:23,387 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:10:23,698 WARN ]: Spent 182.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-22 15:10:23,990 WARN ]: Spent 217.00 ms on a formula simplification that was a NOOP. DAG size: 20 [2018-06-22 15:10:24,099 WARN ]: Spent 102.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2018-06-22 15:10:24,193 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 15:10:24,193 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:10:24,193 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:10:24,203 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 15:10:24,285 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 15:10:24,285 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:10:24,290 INFO ]: Computing forward predicates... [2018-06-22 15:10:24,383 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 15:10:24,402 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:10:24,402 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 8 [2018-06-22 15:10:24,402 INFO ]: Interpolant automaton has 8 states [2018-06-22 15:10:24,402 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 15:10:24,402 INFO ]: CoverageRelationStatistics Valid=19, Invalid=37, Unknown=0, NotChecked=0, Total=56 [2018-06-22 15:10:24,403 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 8 states. [2018-06-22 15:10:24,784 WARN ]: Spent 344.00 ms on a formula simplification that was a NOOP. DAG size: 23 [2018-06-22 15:10:24,847 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:10:24,847 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-22 15:10:24,847 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 15:10:24,847 INFO ]: Start accepts. Automaton has 8 states. Word has length 17 [2018-06-22 15:10:24,848 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:10:24,848 INFO ]: With dead ends: 17 [2018-06-22 15:10:24,848 INFO ]: Without dead ends: 17 [2018-06-22 15:10:24,848 INFO ]: 0 DeclaredPredicates, 26 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=31, Invalid=59, Unknown=0, NotChecked=0, Total=90 [2018-06-22 15:10:24,849 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 15:10:24,851 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-22 15:10:24,851 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 15:10:24,852 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-22 15:10:24,852 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-22 15:10:24,852 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:10:24,852 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-22 15:10:24,852 INFO ]: Interpolant automaton has 8 states. [2018-06-22 15:10:24,852 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-22 15:10:24,853 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 15:10:24,853 INFO ]: Found error trace [2018-06-22 15:10:24,853 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:10:24,853 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:10:24,853 INFO ]: Analyzing trace with hash 2119922091, now seen corresponding path program 3 times [2018-06-22 15:10:24,853 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:10:24,853 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:10:24,854 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:10:24,854 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:10:24,854 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:10:24,901 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:10:25,152 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 15:10:25,152 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:10:25,153 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:10:25,162 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 15:10:25,239 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 15:10:25,239 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:10:25,243 INFO ]: Computing forward predicates... [2018-06-22 15:10:25,523 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 15:10:25,553 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:10:25,553 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 10 [2018-06-22 15:10:25,553 INFO ]: Interpolant automaton has 10 states [2018-06-22 15:10:25,553 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-22 15:10:25,553 INFO ]: CoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2018-06-22 15:10:25,554 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 10 states. [2018-06-22 15:10:25,895 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:10:25,895 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 15:10:25,898 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 15:10:25,898 INFO ]: Start accepts. Automaton has 10 states. Word has length 21 [2018-06-22 15:10:25,898 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:10:25,899 INFO ]: With dead ends: 19 [2018-06-22 15:10:25,899 INFO ]: Without dead ends: 19 [2018-06-22 15:10:25,899 INFO ]: 0 DeclaredPredicates, 34 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=56, Invalid=126, Unknown=0, NotChecked=0, Total=182 [2018-06-22 15:10:25,899 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 15:10:25,902 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 15:10:25,902 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 15:10:25,903 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 15:10:25,903 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-22 15:10:25,903 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:10:25,903 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 15:10:25,903 INFO ]: Interpolant automaton has 10 states. [2018-06-22 15:10:25,903 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 15:10:25,904 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 15:10:25,904 INFO ]: Found error trace [2018-06-22 15:10:25,904 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:10:25,904 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:10:25,904 INFO ]: Analyzing trace with hash 1762711629, now seen corresponding path program 4 times [2018-06-22 15:10:25,904 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:10:25,904 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:10:25,905 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:10:25,905 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:10:25,905 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:10:25,949 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:10:26,309 WARN ]: Spent 181.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-22 15:10:26,727 WARN ]: Spent 340.00 ms on a formula simplification that was a NOOP. DAG size: 21 [2018-06-22 15:10:26,996 WARN ]: Spent 164.00 ms on a formula simplification that was a NOOP. DAG size: 19 [2018-06-22 15:10:27,099 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 15:10:27,099 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:10:27,099 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:10:27,104 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 15:10:27,193 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 15:10:27,193 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:10:27,199 INFO ]: Computing forward predicates... [2018-06-22 15:10:27,562 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 15:10:27,581 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:10:27,581 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 12 [2018-06-22 15:10:27,582 INFO ]: Interpolant automaton has 12 states [2018-06-22 15:10:27,582 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-22 15:10:27,582 INFO ]: CoverageRelationStatistics Valid=33, Invalid=99, Unknown=0, NotChecked=0, Total=132 [2018-06-22 15:10:27,582 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 12 states. [2018-06-22 15:10:27,990 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:10:27,990 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-22 15:10:27,993 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 15:10:27,993 INFO ]: Start accepts. Automaton has 12 states. Word has length 25 [2018-06-22 15:10:27,993 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:10:27,994 INFO ]: With dead ends: 21 [2018-06-22 15:10:27,994 INFO ]: Without dead ends: 21 [2018-06-22 15:10:27,994 INFO ]: 0 DeclaredPredicates, 41 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=77, Invalid=195, Unknown=0, NotChecked=0, Total=272 [2018-06-22 15:10:27,994 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 15:10:28,000 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-22 15:10:28,000 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 15:10:28,000 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-22 15:10:28,001 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-22 15:10:28,001 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:10:28,001 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-22 15:10:28,001 INFO ]: Interpolant automaton has 12 states. [2018-06-22 15:10:28,001 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-22 15:10:28,001 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 15:10:28,001 INFO ]: Found error trace [2018-06-22 15:10:28,001 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:10:28,002 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:10:28,002 INFO ]: Analyzing trace with hash 853117551, now seen corresponding path program 5 times [2018-06-22 15:10:28,002 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:10:28,002 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:10:28,002 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:10:28,002 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:10:28,002 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:10:28,053 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:10:28,686 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 15:10:28,686 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:10:28,686 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:10:28,691 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 15:10:28,809 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-22 15:10:28,809 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:10:28,815 INFO ]: Computing forward predicates... [2018-06-22 15:10:29,183 WARN ]: Spent 286.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 19 [2018-06-22 15:10:29,338 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 15:10:29,357 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:10:29,357 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 15 [2018-06-22 15:10:29,357 INFO ]: Interpolant automaton has 15 states [2018-06-22 15:10:29,358 INFO ]: Constructing interpolant automaton starting with 15 interpolants. [2018-06-22 15:10:29,358 INFO ]: CoverageRelationStatistics Valid=49, Invalid=161, Unknown=0, NotChecked=0, Total=210 [2018-06-22 15:10:29,358 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 15 states. [2018-06-22 15:10:29,561 WARN ]: Spent 177.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 41 [2018-06-22 15:10:30,021 WARN ]: Spent 116.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 34 [2018-06-22 15:10:30,049 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:10:30,049 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-22 15:10:30,051 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 15:10:30,051 INFO ]: Start accepts. Automaton has 15 states. Word has length 29 [2018-06-22 15:10:30,051 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:10:30,052 INFO ]: With dead ends: 23 [2018-06-22 15:10:30,052 INFO ]: Without dead ends: 23 [2018-06-22 15:10:30,052 INFO ]: 0 DeclaredPredicates, 48 GetRequests, 28 SyntacticMatches, 1 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 32 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=115, Invalid=305, Unknown=0, NotChecked=0, Total=420 [2018-06-22 15:10:30,052 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-22 15:10:30,055 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-22 15:10:30,056 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-22 15:10:30,056 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-22 15:10:30,056 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-22 15:10:30,057 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:10:30,057 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-22 15:10:30,057 INFO ]: Interpolant automaton has 15 states. [2018-06-22 15:10:30,057 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-22 15:10:30,058 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-22 15:10:30,058 INFO ]: Found error trace [2018-06-22 15:10:30,058 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:10:30,058 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:10:30,058 INFO ]: Analyzing trace with hash -1661294575, now seen corresponding path program 6 times [2018-06-22 15:10:30,058 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:10:30,058 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:10:30,059 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:10:30,059 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:10:30,059 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:10:30,113 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:10:30,751 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 15:10:30,751 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:10:30,751 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:10:30,759 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 15:10:30,878 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-22 15:10:30,878 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:10:30,884 INFO ]: Computing forward predicates... [2018-06-22 15:10:31,085 WARN ]: Spent 149.00 ms on a formula simplification. DAG size of input: 37 DAG size of output: 22 [2018-06-22 15:10:32,562 WARN ]: Spent 1.16 s on a formula simplification. DAG size of input: 40 DAG size of output: 30 [2018-06-22 15:10:33,009 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 15:10:33,040 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:10:33,040 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 20 [2018-06-22 15:10:33,040 INFO ]: Interpolant automaton has 20 states [2018-06-22 15:10:33,040 INFO ]: Constructing interpolant automaton starting with 20 interpolants. [2018-06-22 15:10:33,041 INFO ]: CoverageRelationStatistics Valid=70, Invalid=310, Unknown=0, NotChecked=0, Total=380 [2018-06-22 15:10:33,041 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 20 states. [2018-06-22 15:10:33,681 WARN ]: Spent 613.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 49 [2018-06-22 15:10:33,879 WARN ]: Spent 132.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 24 [2018-06-22 15:10:34,263 WARN ]: Spent 246.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 24 [2018-06-22 15:10:34,399 WARN ]: Spent 117.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 27 [2018-06-22 15:10:34,600 WARN ]: Spent 182.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 36 [2018-06-22 15:10:34,840 WARN ]: Spent 206.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 42 [2018-06-22 15:10:34,981 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:10:34,981 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-22 15:10:34,982 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 15:10:34,982 INFO ]: Start accepts. Automaton has 20 states. Word has length 33 [2018-06-22 15:10:34,982 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:10:34,983 INFO ]: With dead ends: 25 [2018-06-22 15:10:34,983 INFO ]: Without dead ends: 25 [2018-06-22 15:10:34,983 INFO ]: 0 DeclaredPredicates, 55 GetRequests, 28 SyntacticMatches, 2 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 80 ImplicationChecksByTransitivity, 3.9s TimeCoverageRelationStatistics Valid=168, Invalid=534, Unknown=0, NotChecked=0, Total=702 [2018-06-22 15:10:34,983 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-22 15:10:34,986 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-22 15:10:34,986 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-22 15:10:34,987 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-22 15:10:34,987 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-22 15:10:34,987 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:10:34,987 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-22 15:10:34,987 INFO ]: Interpolant automaton has 20 states. [2018-06-22 15:10:34,987 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-22 15:10:34,988 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-22 15:10:34,988 INFO ]: Found error trace [2018-06-22 15:10:34,988 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:10:34,988 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:10:34,988 INFO ]: Analyzing trace with hash -1494134477, now seen corresponding path program 7 times [2018-06-22 15:10:34,988 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:10:34,988 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:10:34,989 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:10:34,989 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:10:34,989 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:10:35,066 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:10:35,668 INFO ]: Checked inductivity of 105 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-22 15:10:35,668 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:10:35,668 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-22 15:10:35,682 INFO ]: Keeping assertion order NOT_INCREMENTALLY Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:10:35,766 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:10:35,773 INFO ]: Computing forward predicates... [2018-06-22 15:10:36,045 WARN ]: Spent 170.00 ms on a formula simplification. DAG size of input: 38 DAG size of output: 19 [2018-06-22 15:10:36,263 WARN ]: Spent 119.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 35 [2018-06-22 15:10:36,826 INFO ]: Checked inductivity of 105 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-22 15:10:36,847 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:10:36,847 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 20 [2018-06-22 15:10:36,847 INFO ]: Interpolant automaton has 20 states [2018-06-22 15:10:36,847 INFO ]: Constructing interpolant automaton starting with 20 interpolants. [2018-06-22 15:10:36,847 INFO ]: CoverageRelationStatistics Valid=66, Invalid=314, Unknown=0, NotChecked=0, Total=380 [2018-06-22 15:10:36,847 INFO ]: Start difference. First operand 25 states and 26 transitions. Second operand 20 states. [2018-06-22 15:10:37,415 WARN ]: Spent 539.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 48 [2018-06-22 15:10:37,623 WARN ]: Spent 177.00 ms on a formula simplification. DAG size of input: 51 DAG size of output: 24 [2018-06-22 15:10:37,908 WARN ]: Spent 266.00 ms on a formula simplification. DAG size of input: 51 DAG size of output: 22 [2018-06-22 15:10:38,085 WARN ]: Spent 114.00 ms on a formula simplification. DAG size of input: 51 DAG size of output: 25 [2018-06-22 15:10:38,241 WARN ]: Spent 135.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 30 [2018-06-22 15:10:38,481 WARN ]: Spent 219.00 ms on a formula simplification. DAG size of input: 55 DAG size of output: 37 [2018-06-22 15:10:38,933 WARN ]: Spent 304.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 31 [2018-06-22 15:10:39,316 WARN ]: Spent 347.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 45 [2018-06-22 15:10:39,384 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:10:39,384 INFO ]: Finished difference Result 27 states and 28 transitions. [2018-06-22 15:10:39,385 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-22 15:10:39,385 INFO ]: Start accepts. Automaton has 20 states. Word has length 37 [2018-06-22 15:10:39,386 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:10:39,386 INFO ]: With dead ends: 27 [2018-06-22 15:10:39,386 INFO ]: Without dead ends: 27 [2018-06-22 15:10:39,387 INFO ]: 0 DeclaredPredicates, 62 GetRequests, 35 SyntacticMatches, 1 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 64 ImplicationChecksByTransitivity, 3.3s TimeCoverageRelationStatistics Valid=180, Invalid=576, Unknown=0, NotChecked=0, Total=756 [2018-06-22 15:10:39,387 INFO ]: Start minimizeSevpa. Operand 27 states. [2018-06-22 15:10:39,393 INFO ]: Finished minimizeSevpa. Reduced states from 27 to 27. [2018-06-22 15:10:39,393 INFO ]: Start removeUnreachable. Operand 27 states. [2018-06-22 15:10:39,393 INFO ]: Finished removeUnreachable. Reduced from 27 states to 27 states and 28 transitions. [2018-06-22 15:10:39,393 INFO ]: Start accepts. Automaton has 27 states and 28 transitions. Word has length 37 [2018-06-22 15:10:39,394 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:10:39,394 INFO ]: Abstraction has 27 states and 28 transitions. [2018-06-22 15:10:39,394 INFO ]: Interpolant automaton has 20 states. [2018-06-22 15:10:39,394 INFO ]: Start isEmpty. Operand 27 states and 28 transitions. [2018-06-22 15:10:39,394 INFO ]: Finished isEmpty. Found accepting run of length 42 [2018-06-22 15:10:39,394 INFO ]: Found error trace [2018-06-22 15:10:39,394 INFO ]: trace histogram [9, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:10:39,395 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:10:39,395 INFO ]: Analyzing trace with hash 1618126293, now seen corresponding path program 8 times [2018-06-22 15:10:39,395 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:10:39,395 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:10:39,395 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:10:39,395 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:10:39,395 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:10:39,460 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:10:39,830 WARN ]: Spent 101.00 ms on a formula simplification that was a NOOP. DAG size: 15 [2018-06-22 15:10:40,268 INFO ]: Checked inductivity of 136 backedges. 0 proven. 100 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2018-06-22 15:10:40,268 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:10:40,268 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:10:40,274 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 15:10:40,398 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 15:10:40,398 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:10:40,405 INFO ]: Computing forward predicates... [2018-06-22 15:10:40,717 WARN ]: Spent 121.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 35 [2018-06-22 15:10:41,158 INFO ]: Checked inductivity of 136 backedges. 0 proven. 100 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2018-06-22 15:10:41,180 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:10:41,180 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 20] total 24 [2018-06-22 15:10:41,180 INFO ]: Interpolant automaton has 24 states [2018-06-22 15:10:41,180 INFO ]: Constructing interpolant automaton starting with 24 interpolants. [2018-06-22 15:10:41,181 INFO ]: CoverageRelationStatistics Valid=87, Invalid=465, Unknown=0, NotChecked=0, Total=552 [2018-06-22 15:10:41,181 INFO ]: Start difference. First operand 27 states and 28 transitions. Second operand 24 states. [2018-06-22 15:10:41,672 WARN ]: Spent 454.00 ms on a formula simplification. DAG size of input: 60 DAG size of output: 46 [2018-06-22 15:10:41,848 WARN ]: Spent 145.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 25 [2018-06-22 15:10:42,225 WARN ]: Spent 130.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 26 [2018-06-22 15:10:42,598 WARN ]: Spent 284.00 ms on a formula simplification. DAG size of input: 58 DAG size of output: 36 [2018-06-22 15:10:42,864 WARN ]: Spent 242.00 ms on a formula simplification. DAG size of input: 57 DAG size of output: 32 [2018-06-22 15:10:43,138 WARN ]: Spent 250.00 ms on a formula simplification. DAG size of input: 57 DAG size of output: 32 [2018-06-22 15:10:43,557 WARN ]: Spent 384.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 45 [2018-06-22 15:10:43,603 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:10:43,603 INFO ]: Finished difference Result 29 states and 30 transitions. [2018-06-22 15:10:43,611 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-22 15:10:43,611 INFO ]: Start accepts. Automaton has 24 states. Word has length 41 [2018-06-22 15:10:43,611 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:10:43,612 INFO ]: With dead ends: 29 [2018-06-22 15:10:43,612 INFO ]: Without dead ends: 29 [2018-06-22 15:10:43,612 INFO ]: 0 DeclaredPredicates, 69 GetRequests, 36 SyntacticMatches, 2 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 108 ImplicationChecksByTransitivity, 3.2s TimeCoverageRelationStatistics Valid=233, Invalid=823, Unknown=0, NotChecked=0, Total=1056 [2018-06-22 15:10:43,612 INFO ]: Start minimizeSevpa. Operand 29 states. [2018-06-22 15:10:43,616 INFO ]: Finished minimizeSevpa. Reduced states from 29 to 29. [2018-06-22 15:10:43,616 INFO ]: Start removeUnreachable. Operand 29 states. [2018-06-22 15:10:43,616 INFO ]: Finished removeUnreachable. Reduced from 29 states to 29 states and 30 transitions. [2018-06-22 15:10:43,616 INFO ]: Start accepts. Automaton has 29 states and 30 transitions. Word has length 41 [2018-06-22 15:10:43,616 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:10:43,616 INFO ]: Abstraction has 29 states and 30 transitions. [2018-06-22 15:10:43,616 INFO ]: Interpolant automaton has 24 states. [2018-06-22 15:10:43,616 INFO ]: Start isEmpty. Operand 29 states and 30 transitions. [2018-06-22 15:10:43,617 INFO ]: Finished isEmpty. Found accepting run of length 46 [2018-06-22 15:10:43,617 INFO ]: Found error trace [2018-06-22 15:10:43,617 INFO ]: trace histogram [10, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:10:43,617 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:10:43,617 INFO ]: Analyzing trace with hash 996918775, now seen corresponding path program 9 times [2018-06-22 15:10:43,617 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:10:43,617 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:10:43,618 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:10:43,618 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:10:43,618 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:10:43,706 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:10:44,517 WARN ]: Spent 548.00 ms on a formula simplification that was a NOOP. DAG size: 20 [2018-06-22 15:10:45,039 INFO ]: Checked inductivity of 171 backedges. 0 proven. 126 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-06-22 15:10:45,039 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:10:45,039 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:10:45,044 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 15:10:45,181 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2018-06-22 15:10:45,181 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:10:45,189 INFO ]: Computing forward predicates... [2018-06-22 15:10:46,353 WARN ]: Spent 797.00 ms on a formula simplification. DAG size of input: 225 DAG size of output: 39 [2018-06-22 15:10:47,872 WARN ]: Spent 1.27 s on a formula simplification. DAG size of input: 164 DAG size of output: 75 [2018-06-22 15:10:48,072 WARN ]: Spent 118.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 35 [2018-06-22 15:10:52,452 INFO ]: Checked inductivity of 171 backedges. 0 proven. 126 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-06-22 15:10:52,474 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:10:52,474 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22] total 28 [2018-06-22 15:10:52,474 INFO ]: Interpolant automaton has 28 states [2018-06-22 15:10:52,474 INFO ]: Constructing interpolant automaton starting with 28 interpolants. [2018-06-22 15:10:52,475 INFO ]: CoverageRelationStatistics Valid=102, Invalid=654, Unknown=0, NotChecked=0, Total=756 [2018-06-22 15:10:52,475 INFO ]: Start difference. First operand 29 states and 30 transitions. Second operand 28 states. [2018-06-22 15:10:54,419 WARN ]: Spent 1.90 s on a formula simplification. DAG size of input: 128 DAG size of output: 99 [2018-06-22 15:10:55,064 WARN ]: Spent 592.00 ms on a formula simplification. DAG size of input: 102 DAG size of output: 62 [2018-06-22 15:10:55,775 WARN ]: Spent 675.00 ms on a formula simplification. DAG size of input: 100 DAG size of output: 48 [2018-06-22 15:10:56,297 WARN ]: Spent 487.00 ms on a formula simplification. DAG size of input: 100 DAG size of output: 53 [2018-06-22 15:10:56,799 WARN ]: Spent 464.00 ms on a formula simplification. DAG size of input: 102 DAG size of output: 43 [2018-06-22 15:10:57,780 WARN ]: Spent 879.00 ms on a formula simplification. DAG size of input: 106 DAG size of output: 56 [2018-06-22 15:10:58,359 WARN ]: Spent 530.00 ms on a formula simplification. DAG size of input: 103 DAG size of output: 58 [2018-06-22 15:10:58,982 WARN ]: Spent 526.00 ms on a formula simplification. DAG size of input: 103 DAG size of output: 57 [2018-06-22 15:11:00,032 WARN ]: Spent 1.01 s on a formula simplification. DAG size of input: 107 DAG size of output: 66 [2018-06-22 15:11:01,492 WARN ]: Spent 1.40 s on a formula simplification. DAG size of input: 102 DAG size of output: 77 [2018-06-22 15:11:01,539 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:11:01,539 INFO ]: Finished difference Result 31 states and 32 transitions. [2018-06-22 15:11:01,539 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-22 15:11:01,539 INFO ]: Start accepts. Automaton has 28 states. Word has length 45 [2018-06-22 15:11:01,539 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:11:01,540 INFO ]: With dead ends: 31 [2018-06-22 15:11:01,540 INFO ]: Without dead ends: 31 [2018-06-22 15:11:01,541 INFO ]: 0 DeclaredPredicates, 76 GetRequests, 37 SyntacticMatches, 3 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 169 ImplicationChecksByTransitivity, 13.0s TimeCoverageRelationStatistics Valid=295, Invalid=1111, Unknown=0, NotChecked=0, Total=1406 [2018-06-22 15:11:01,541 INFO ]: Start minimizeSevpa. Operand 31 states. [2018-06-22 15:11:01,544 INFO ]: Finished minimizeSevpa. Reduced states from 31 to 31. [2018-06-22 15:11:01,544 INFO ]: Start removeUnreachable. Operand 31 states. [2018-06-22 15:11:01,550 INFO ]: Finished removeUnreachable. Reduced from 31 states to 31 states and 32 transitions. [2018-06-22 15:11:01,550 INFO ]: Start accepts. Automaton has 31 states and 32 transitions. Word has length 45 [2018-06-22 15:11:01,550 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:11:01,550 INFO ]: Abstraction has 31 states and 32 transitions. [2018-06-22 15:11:01,550 INFO ]: Interpolant automaton has 28 states. [2018-06-22 15:11:01,550 INFO ]: Start isEmpty. Operand 31 states and 32 transitions. [2018-06-22 15:11:01,551 INFO ]: Finished isEmpty. Found accepting run of length 50 [2018-06-22 15:11:01,551 INFO ]: Found error trace [2018-06-22 15:11:01,551 INFO ]: trace histogram [11, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:11:01,551 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:11:01,551 INFO ]: Analyzing trace with hash -570306151, now seen corresponding path program 10 times [2018-06-22 15:11:01,551 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:11:01,551 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:11:01,552 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:11:01,552 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:11:01,552 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:11:01,650 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:11:02,555 INFO ]: Checked inductivity of 210 backedges. 0 proven. 155 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2018-06-22 15:11:02,555 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:11:02,555 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:11:02,561 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 15:11:02,707 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 15:11:02,707 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:11:02,717 INFO ]: Computing forward predicates... [2018-06-22 15:11:03,071 WARN ]: Spent 221.00 ms on a formula simplification. DAG size of input: 60 DAG size of output: 26 [2018-06-22 15:11:03,301 WARN ]: Spent 193.00 ms on a formula simplification. DAG size of input: 43 DAG size of output: 35 [2018-06-22 15:11:03,588 WARN ]: Spent 119.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 35 [2018-06-22 15:11:04,002 INFO ]: Checked inductivity of 210 backedges. 0 proven. 155 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2018-06-22 15:11:04,021 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:11:04,021 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 24] total 30 [2018-06-22 15:11:04,022 INFO ]: Interpolant automaton has 30 states [2018-06-22 15:11:04,022 INFO ]: Constructing interpolant automaton starting with 30 interpolants. [2018-06-22 15:11:04,022 INFO ]: CoverageRelationStatistics Valid=97, Invalid=773, Unknown=0, NotChecked=0, Total=870 [2018-06-22 15:11:04,022 INFO ]: Start difference. First operand 31 states and 32 transitions. Second operand 30 states. [2018-06-22 15:11:05,143 WARN ]: Spent 1.07 s on a formula simplification. DAG size of input: 88 DAG size of output: 71 [2018-06-22 15:11:05,471 WARN ]: Spent 254.00 ms on a formula simplification. DAG size of input: 86 DAG size of output: 29 [2018-06-22 15:11:05,709 WARN ]: Spent 202.00 ms on a formula simplification. DAG size of input: 86 DAG size of output: 27 [2018-06-22 15:11:05,961 WARN ]: Spent 218.00 ms on a formula simplification. DAG size of input: 86 DAG size of output: 31 [2018-06-22 15:11:06,280 WARN ]: Spent 284.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 34 [2018-06-22 15:11:06,751 WARN ]: Spent 435.00 ms on a formula simplification. DAG size of input: 91 DAG size of output: 41 [2018-06-22 15:11:07,098 WARN ]: Spent 313.00 ms on a formula simplification. DAG size of input: 89 DAG size of output: 34 [2018-06-22 15:11:07,503 WARN ]: Spent 371.00 ms on a formula simplification. DAG size of input: 89 DAG size of output: 37 [2018-06-22 15:11:07,942 WARN ]: Spent 396.00 ms on a formula simplification. DAG size of input: 91 DAG size of output: 39 [2018-06-22 15:11:08,409 WARN ]: Spent 432.00 ms on a formula simplification. DAG size of input: 90 DAG size of output: 41 [2018-06-22 15:11:09,598 WARN ]: Spent 1.13 s on a formula simplification. DAG size of input: 89 DAG size of output: 67 [2018-06-22 15:11:09,638 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:11:09,670 INFO ]: Finished difference Result 33 states and 34 transitions. [2018-06-22 15:11:09,670 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-06-22 15:11:09,670 INFO ]: Start accepts. Automaton has 30 states. Word has length 49 [2018-06-22 15:11:09,671 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:11:09,671 INFO ]: With dead ends: 33 [2018-06-22 15:11:09,671 INFO ]: Without dead ends: 33 [2018-06-22 15:11:09,672 INFO ]: 0 DeclaredPredicates, 83 GetRequests, 41 SyntacticMatches, 3 SemanticMatches, 39 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 195 ImplicationChecksByTransitivity, 7.0s TimeCoverageRelationStatistics Valid=321, Invalid=1319, Unknown=0, NotChecked=0, Total=1640 [2018-06-22 15:11:09,672 INFO ]: Start minimizeSevpa. Operand 33 states. [2018-06-22 15:11:09,676 INFO ]: Finished minimizeSevpa. Reduced states from 33 to 33. [2018-06-22 15:11:09,676 INFO ]: Start removeUnreachable. Operand 33 states. [2018-06-22 15:11:09,676 INFO ]: Finished removeUnreachable. Reduced from 33 states to 33 states and 34 transitions. [2018-06-22 15:11:09,676 INFO ]: Start accepts. Automaton has 33 states and 34 transitions. Word has length 49 [2018-06-22 15:11:09,677 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:11:09,677 INFO ]: Abstraction has 33 states and 34 transitions. [2018-06-22 15:11:09,677 INFO ]: Interpolant automaton has 30 states. [2018-06-22 15:11:09,677 INFO ]: Start isEmpty. Operand 33 states and 34 transitions. [2018-06-22 15:11:09,678 INFO ]: Finished isEmpty. Found accepting run of length 54 [2018-06-22 15:11:09,678 INFO ]: Found error trace [2018-06-22 15:11:09,678 INFO ]: trace histogram [12, 11, 11, 11, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:11:09,678 INFO ]: === Iteration 12 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:11:09,678 INFO ]: Analyzing trace with hash 1955719355, now seen corresponding path program 11 times [2018-06-22 15:11:09,678 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:11:09,678 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:11:09,678 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:11:09,678 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:11:09,678 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:11:09,801 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:11:10,861 WARN ]: Spent 683.00 ms on a formula simplification. DAG size of input: 84 DAG size of output: 28 [2018-06-22 15:11:11,884 WARN ]: Spent 995.00 ms on a formula simplification. DAG size of input: 236 DAG size of output: 110 [2018-06-22 15:11:13,557 WARN ]: Spent 749.00 ms on a formula simplification. DAG size of input: 93 DAG size of output: 37 [2018-06-22 15:11:13,585 INFO ]: Checked inductivity of 253 backedges. 0 proven. 187 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2018-06-22 15:11:13,586 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:11:13,586 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:11:13,591 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 15:11:13,749 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 12 check-sat command(s) [2018-06-22 15:11:13,749 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:11:13,758 INFO ]: Computing forward predicates... [2018-06-22 15:11:13,954 WARN ]: Spent 127.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 22 [2018-06-22 15:11:14,183 WARN ]: Spent 190.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 38 [2018-06-22 15:11:14,446 WARN ]: Spent 213.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 41 [2018-06-22 15:11:14,947 WARN ]: Spent 423.00 ms on a formula simplification. DAG size of input: 63 DAG size of output: 36 [2018-06-22 15:11:15,284 WARN ]: Spent 173.00 ms on a formula simplification. DAG size of input: 52 DAG size of output: 40 [2018-06-22 15:11:16,640 INFO ]: Checked inductivity of 253 backedges. 0 proven. 187 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2018-06-22 15:11:16,661 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:11:16,661 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [26, 26] total 41 [2018-06-22 15:11:16,662 INFO ]: Interpolant automaton has 41 states [2018-06-22 15:11:16,662 INFO ]: Constructing interpolant automaton starting with 41 interpolants. [2018-06-22 15:11:16,662 INFO ]: CoverageRelationStatistics Valid=156, Invalid=1484, Unknown=0, NotChecked=0, Total=1640 [2018-06-22 15:11:16,662 INFO ]: Start difference. First operand 33 states and 34 transitions. Second operand 41 states. [2018-06-22 15:11:18,608 WARN ]: Spent 1.84 s on a formula simplification. DAG size of input: 222 DAG size of output: 151 [2018-06-22 15:11:18,947 WARN ]: Spent 251.00 ms on a formula simplification. DAG size of input: 199 DAG size of output: 35 [2018-06-22 15:11:19,311 WARN ]: Spent 283.00 ms on a formula simplification. DAG size of input: 201 DAG size of output: 38 [2018-06-22 15:11:19,690 WARN ]: Spent 321.00 ms on a formula simplification. DAG size of input: 201 DAG size of output: 38 [2018-06-22 15:11:20,192 WARN ]: Spent 402.00 ms on a formula simplification. DAG size of input: 203 DAG size of output: 42 [2018-06-22 15:11:20,794 WARN ]: Spent 533.00 ms on a formula simplification. DAG size of input: 203 DAG size of output: 59 [2018-06-22 15:11:21,473 WARN ]: Spent 564.00 ms on a formula simplification. DAG size of input: 202 DAG size of output: 57 [2018-06-22 15:11:22,149 WARN ]: Spent 606.00 ms on a formula simplification. DAG size of input: 203 DAG size of output: 61 [2018-06-22 15:11:22,794 WARN ]: Spent 577.00 ms on a formula simplification. DAG size of input: 206 DAG size of output: 69 Received shutdown request... [2018-06-22 15:11:23,219 WARN ]: Removed 10 from assertion stack [2018-06-22 15:11:23,220 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-22 15:11:23,220 WARN ]: Verification canceled [2018-06-22 15:11:23,223 WARN ]: Timeout [2018-06-22 15:11:23,223 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 03:11:23 BoogieIcfgContainer [2018-06-22 15:11:23,223 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 15:11:23,224 INFO ]: Toolchain (without parser) took 61843.97 ms. Allocated memory was 309.9 MB in the beginning and 936.9 MB in the end (delta: 627.0 MB). Free memory was 256.2 MB in the beginning and 647.2 MB in the end (delta: -391.0 MB). Peak memory consumption was 236.1 MB. Max. memory is 3.6 GB. [2018-06-22 15:11:23,225 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 309.9 MB. Free memory is still 275.3 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 15:11:23,225 INFO ]: ChcToBoogie took 53.25 ms. Allocated memory is still 309.9 MB. Free memory was 256.2 MB in the beginning and 254.3 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:11:23,225 INFO ]: Boogie Preprocessor took 60.40 ms. Allocated memory is still 309.9 MB. Free memory was 254.3 MB in the beginning and 252.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:11:23,226 INFO ]: RCFGBuilder took 320.02 ms. Allocated memory is still 309.9 MB. Free memory was 252.2 MB in the beginning and 239.2 MB in the end (delta: 13.0 MB). Peak memory consumption was 13.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:11:23,226 INFO ]: TraceAbstraction took 61401.23 ms. Allocated memory was 309.9 MB in the beginning and 936.9 MB in the end (delta: 627.0 MB). Free memory was 239.2 MB in the beginning and 647.2 MB in the end (delta: -408.0 MB). Peak memory consumption was 219.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:11:23,232 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.07 ms. Allocated memory is still 309.9 MB. Free memory is still 275.3 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 53.25 ms. Allocated memory is still 309.9 MB. Free memory was 256.2 MB in the beginning and 254.3 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 60.40 ms. Allocated memory is still 309.9 MB. Free memory was 254.3 MB in the beginning and 252.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 320.02 ms. Allocated memory is still 309.9 MB. Free memory was 252.2 MB in the beginning and 239.2 MB in the end (delta: 13.0 MB). Peak memory consumption was 13.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 61401.23 ms. Allocated memory was 309.9 MB in the beginning and 936.9 MB in the end (delta: 627.0 MB). Free memory was 239.2 MB in the beginning and 647.2 MB in the end (delta: -408.0 MB). Peak memory consumption was 219.0 MB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was constructing difference of abstraction (33states) and interpolant automaton (currently 13 states, 41 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 209. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 61.3s OverallTime, 12 OverallIterations, 12 TraceHistogramMax, 30.3s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 171 SDtfs, 677 SDslu, 1100 SDs, 0 SdLazy, 1079 SolverSat, 791 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 1.6s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 604 GetRequests, 324 SyntacticMatches, 14 SemanticMatches, 265 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 992 ImplicationChecksByTransitivity, 46.5s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=33occurred in iteration=11, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 11 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.2s SsaConstructionTime, 1.8s SatisfiabilityAnalysisTime, 28.2s InterpolantComputationTime, 735 NumberOfCodeBlocks, 735 NumberOfCodeBlocksAsserted, 61 NumberOfCheckSat, 712 ConstructedInterpolants, 0 QuantifiedInterpolants, 7988260 SizeOfPredicates, 1486 NumberOfNonLiveVariables, 5060 ConjunctsInSsa, 632 ConjunctsInUnsatCore, 23 InterpolantComputations, 1 PerfectInterpolantSequences, 572/2156 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/large_const.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_15-11-23-246.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/large_const.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_15-11-23-246.csv Completed graceful shutdown