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/efm.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 15:01:34,855 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 15:01:34,857 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 15:01:34,869 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 15:01:34,869 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 15:01:34,870 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 15:01:34,874 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 15:01:34,876 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 15:01:34,877 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 15:01:34,879 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 15:01:34,880 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 15:01:34,880 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 15:01:34,881 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 15:01:34,882 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 15:01:34,882 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 15:01:34,885 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 15:01:34,887 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 15:01:34,889 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 15:01:34,899 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 15:01:34,900 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 15:01:34,901 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 15:01:34,903 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 15:01:34,904 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 15:01:34,904 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 15:01:34,905 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 15:01:34,905 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 15:01:34,906 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 15:01:34,907 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 15:01:34,908 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 15:01:34,908 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 15:01:34,908 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 15:01:34,912 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 15:01:34,912 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 15:01:34,913 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 15:01:34,913 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 15:01:34,913 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:01:34,930 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 15:01:34,931 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 15:01:34,931 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 15:01:34,931 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 15:01:34,932 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 15:01:34,932 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 15:01:34,933 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 15:01:34,933 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 15:01:34,933 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 15:01:34,933 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 15:01:34,933 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 15:01:34,934 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 15:01:34,934 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 15:01:34,934 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 15:01:34,934 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 15:01:34,934 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 15:01:34,934 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 15:01:34,935 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 15:01:34,935 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 15:01:34,936 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 15:01:34,936 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 15:01:34,989 INFO ]: Repository-Root is: /tmp [2018-06-22 15:01:35,004 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 15:01:35,012 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 15:01:35,013 INFO ]: Initializing SmtParser... [2018-06-22 15:01:35,013 INFO ]: SmtParser initialized [2018-06-22 15:01:35,015 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/efm.c.smt2 [2018-06-22 15:01:35,016 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:01:35,104 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/efm.c.smt2 unknown [2018-06-22 15:01:35,614 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/efm.c.smt2 [2018-06-22 15:01:35,619 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 15:01:35,626 INFO ]: Walking toolchain with 4 elements. [2018-06-22 15:01:35,627 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 15:01:35,627 INFO ]: Initializing ChcToBoogie... [2018-06-22 15:01:35,627 INFO ]: ChcToBoogie initialized [2018-06-22 15:01:35,630 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:01:35" (1/1) ... [2018-06-22 15:01:35,681 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:01:35 Unit [2018-06-22 15:01:35,681 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 15:01:35,681 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 15:01:35,681 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 15:01:35,681 INFO ]: Boogie Preprocessor initialized [2018-06-22 15:01:35,704 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:01:35" (1/1) ... [2018-06-22 15:01:35,704 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:01:35" (1/1) ... [2018-06-22 15:01:35,718 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:01:35" (1/1) ... [2018-06-22 15:01:35,718 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:01:35" (1/1) ... [2018-06-22 15:01:35,730 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:01:35" (1/1) ... [2018-06-22 15:01:35,731 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:01:35" (1/1) ... [2018-06-22 15:01:35,734 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:01:35" (1/1) ... [2018-06-22 15:01:35,739 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 15:01:35,740 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 15:01:35,740 INFO ]: Initializing RCFGBuilder... [2018-06-22 15:01:35,740 INFO ]: RCFGBuilder initialized [2018-06-22 15:01:35,740 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:01:35" (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) [2018-06-22 15:01:35,754 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 15:01:35,754 INFO ]: Found specification of procedure False [2018-06-22 15:01:35,754 INFO ]: Found implementation of procedure False [2018-06-22 15:01:35,755 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 15:01:35,755 INFO ]: Found specification of procedure state [2018-06-22 15:01:35,755 INFO ]: Found implementation of procedure state [2018-06-22 15:01:35,755 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 15:01:35,755 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 15:01:35,755 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 15:01:36,121 INFO ]: Using library mode [2018-06-22 15:01:36,122 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:01:36 BoogieIcfgContainer [2018-06-22 15:01:36,122 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 15:01:36,124 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 15:01:36,124 INFO ]: Initializing TraceAbstraction... [2018-06-22 15:01:36,129 INFO ]: TraceAbstraction initialized [2018-06-22 15:01:36,129 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:01:35" (1/3) ... [2018-06-22 15:01:36,130 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@b4ddcff and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 03:01:36, skipping insertion in model container [2018-06-22 15:01:36,130 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:01:35" (2/3) ... [2018-06-22 15:01:36,130 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@b4ddcff and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 03:01:36, skipping insertion in model container [2018-06-22 15:01:36,130 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:01:36" (3/3) ... [2018-06-22 15:01:36,132 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 15:01:36,142 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 15:01:36,152 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 15:01:36,203 INFO ]: Using default assertion order modulation [2018-06-22 15:01:36,204 INFO ]: Interprodecural is true [2018-06-22 15:01:36,204 INFO ]: Hoare is false [2018-06-22 15:01:36,204 INFO ]: Compute interpolants for FPandBP [2018-06-22 15:01:36,204 INFO ]: Backedges is TWOTRACK [2018-06-22 15:01:36,204 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 15:01:36,204 INFO ]: Difference is false [2018-06-22 15:01:36,204 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 15:01:36,204 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 15:01:36,223 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 15:01:36,231 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 15:01:36,231 INFO ]: Found error trace [2018-06-22 15:01:36,232 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:01:36,232 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:01:36,237 INFO ]: Analyzing trace with hash -683425083, now seen corresponding path program 1 times [2018-06-22 15:01:36,239 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:01:36,239 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:01:36,277 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:01:36,277 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:01:36,277 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:01:36,321 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:01:36,423 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:01:36,424 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 15:01:36,424 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 15:01:36,426 INFO ]: Interpolant automaton has 4 states [2018-06-22 15:01:36,441 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 15:01:36,441 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 15:01:36,444 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 15:01:36,571 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:01:36,571 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 15:01:36,571 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 15:01:36,572 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 15:01:36,573 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:01:36,582 INFO ]: With dead ends: 13 [2018-06-22 15:01:36,582 INFO ]: Without dead ends: 13 [2018-06-22 15:01:36,583 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:01:36,596 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 15:01:36,615 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 15:01:36,616 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 15:01:36,617 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 15:01:36,618 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 15:01:36,618 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:01:36,618 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 15:01:36,618 INFO ]: Interpolant automaton has 4 states. [2018-06-22 15:01:36,619 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 15:01:36,620 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 15:01:36,620 INFO ]: Found error trace [2018-06-22 15:01:36,620 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:01:36,620 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:01:36,620 INFO ]: Analyzing trace with hash 204343015, now seen corresponding path program 1 times [2018-06-22 15:01:36,620 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:01:36,620 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:01:36,621 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:01:36,621 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:01:36,621 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:01:36,756 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:01:37,293 WARN ]: Spent 289.00 ms on a formula simplification. DAG size of input: 19 DAG size of output: 16 [2018-06-22 15:01:37,547 WARN ]: Spent 118.00 ms on a formula simplification. DAG size of input: 10 DAG size of output: 7 [2018-06-22 15:01:37,550 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:01:37,550 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:01:37,550 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) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:01:37,557 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:01:37,617 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:01:37,628 INFO ]: Computing forward predicates... [2018-06-22 15:01:38,011 WARN ]: Spent 215.00 ms on a formula simplification. DAG size of input: 17 DAG size of output: 7 [2018-06-22 15:01:38,196 WARN ]: Spent 156.00 ms on a formula simplification. DAG size of input: 18 DAG size of output: 15 [2018-06-22 15:01:38,471 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:01:38,504 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:01:38,504 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-22 15:01:38,505 INFO ]: Interpolant automaton has 9 states [2018-06-22 15:01:38,505 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 15:01:38,505 INFO ]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2018-06-22 15:01:38,505 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 9 states. [2018-06-22 15:01:38,709 WARN ]: Spent 143.00 ms on a formula simplification that was a NOOP. DAG size: 13 [2018-06-22 15:01:39,165 WARN ]: Spent 324.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 19 [2018-06-22 15:01:39,241 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:01:39,241 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 15:01:39,242 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 15:01:39,242 INFO ]: Start accepts. Automaton has 9 states. Word has length 13 [2018-06-22 15:01:39,242 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:01:39,242 INFO ]: With dead ends: 15 [2018-06-22 15:01:39,242 INFO ]: Without dead ends: 15 [2018-06-22 15:01:39,243 INFO ]: 0 DeclaredPredicates, 21 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2018-06-22 15:01:39,243 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 15:01:39,246 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 15:01:39,246 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 15:01:39,247 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 15:01:39,247 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 15:01:39,247 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:01:39,247 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 15:01:39,247 INFO ]: Interpolant automaton has 9 states. [2018-06-22 15:01:39,247 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 15:01:39,247 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 15:01:39,247 INFO ]: Found error trace [2018-06-22 15:01:39,247 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:01:39,248 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:01:39,248 INFO ]: Analyzing trace with hash -1649658231, now seen corresponding path program 2 times [2018-06-22 15:01:39,248 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:01:39,248 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:01:39,249 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:01:39,249 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:01:39,249 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:01:39,335 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:01:39,670 WARN ]: Spent 191.00 ms on a formula simplification. DAG size of input: 21 DAG size of output: 17 [2018-06-22 15:01:39,814 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:01:39,814 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:01:39,814 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) [2018-06-22 15:01:39,828 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:01:39,924 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 15:01:39,924 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:01:39,929 INFO ]: Computing forward predicates... [2018-06-22 15:01:40,286 WARN ]: Spent 151.00 ms on a formula simplification. DAG size of input: 33 DAG size of output: 26 [2018-06-22 15:01:40,405 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:01:40,436 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:01:40,436 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2018-06-22 15:01:40,436 INFO ]: Interpolant automaton has 11 states [2018-06-22 15:01:40,436 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-22 15:01:40,437 INFO ]: CoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2018-06-22 15:01:40,437 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 11 states. [2018-06-22 15:01:40,577 WARN ]: Spent 115.00 ms on a formula simplification. DAG size of input: 31 DAG size of output: 31 [2018-06-22 15:01:40,752 WARN ]: Spent 104.00 ms on a formula simplification. DAG size of input: 33 DAG size of output: 30 [2018-06-22 15:01:40,774 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:01:40,774 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-22 15:01:40,774 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 15:01:40,774 INFO ]: Start accepts. Automaton has 11 states. Word has length 17 [2018-06-22 15:01:40,774 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:01:40,775 INFO ]: With dead ends: 17 [2018-06-22 15:01:40,775 INFO ]: Without dead ends: 17 [2018-06-22 15:01:40,775 INFO ]: 0 DeclaredPredicates, 27 GetRequests, 14 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=46, Invalid=136, Unknown=0, NotChecked=0, Total=182 [2018-06-22 15:01:40,775 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 15:01:40,778 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-22 15:01:40,778 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 15:01:40,778 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-22 15:01:40,779 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-22 15:01:40,779 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:01:40,779 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-22 15:01:40,779 INFO ]: Interpolant automaton has 11 states. [2018-06-22 15:01:40,779 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-22 15:01:40,779 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 15:01:40,779 INFO ]: Found error trace [2018-06-22 15:01:40,779 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:01:40,780 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:01:40,780 INFO ]: Analyzing trace with hash 2119922091, now seen corresponding path program 3 times [2018-06-22 15:01:40,780 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:01:40,780 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:01:40,781 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:01:40,781 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:01:40,781 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:01:40,919 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:01:42,266 WARN ]: Spent 1.14 s on a formula simplification. DAG size of input: 20 DAG size of output: 15 [2018-06-22 15:01:42,528 WARN ]: Spent 192.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 31 [2018-06-22 15:01:42,659 WARN ]: Spent 122.00 ms on a formula simplification. DAG size of input: 24 DAG size of output: 21 [2018-06-22 15:01:42,749 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:01:42,749 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:01:42,749 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:01:42,765 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 15:01:42,862 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 15:01:42,862 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:01:42,868 INFO ]: Computing forward predicates... [2018-06-22 15:01:43,959 WARN ]: Spent 767.00 ms on a formula simplification. DAG size of input: 141 DAG size of output: 33 [2018-06-22 15:01:44,101 WARN ]: Spent 112.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 28 [2018-06-22 15:01:44,262 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:01:44,281 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:01:44,281 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 14 [2018-06-22 15:01:44,282 INFO ]: Interpolant automaton has 14 states [2018-06-22 15:01:44,282 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-22 15:01:44,282 INFO ]: CoverageRelationStatistics Valid=34, Invalid=148, Unknown=0, NotChecked=0, Total=182 [2018-06-22 15:01:44,282 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 14 states. [2018-06-22 15:01:44,727 WARN ]: Spent 393.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 46 [2018-06-22 15:01:44,957 WARN ]: Spent 205.00 ms on a formula simplification. DAG size of input: 43 DAG size of output: 25 [2018-06-22 15:01:45,143 WARN ]: Spent 162.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 28 [2018-06-22 15:01:45,536 WARN ]: Spent 376.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 34 [2018-06-22 15:01:45,561 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:01:45,562 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 15:01:45,563 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 15:01:45,563 INFO ]: Start accepts. Automaton has 14 states. Word has length 21 [2018-06-22 15:01:45,563 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:01:45,563 INFO ]: With dead ends: 19 [2018-06-22 15:01:45,563 INFO ]: Without dead ends: 19 [2018-06-22 15:01:45,564 INFO ]: 0 DeclaredPredicates, 35 GetRequests, 16 SyntacticMatches, 2 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 45 ImplicationChecksByTransitivity, 4.0s TimeCoverageRelationStatistics Valid=75, Invalid=267, Unknown=0, NotChecked=0, Total=342 [2018-06-22 15:01:45,564 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 15:01:45,566 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 15:01:45,566 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 15:01:45,567 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 15:01:45,567 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-22 15:01:45,567 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:01:45,567 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 15:01:45,567 INFO ]: Interpolant automaton has 14 states. [2018-06-22 15:01:45,567 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 15:01:45,568 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 15:01:45,568 INFO ]: Found error trace [2018-06-22 15:01:45,568 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:01:45,568 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:01:45,568 INFO ]: Analyzing trace with hash 1762711629, now seen corresponding path program 4 times [2018-06-22 15:01:45,568 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:01:45,568 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:01:45,569 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:01:45,569 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:01:45,569 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:01:45,679 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:01:46,113 WARN ]: Spent 147.00 ms on a formula simplification. DAG size of input: 14 DAG size of output: 14 [2018-06-22 15:01:46,424 WARN ]: Spent 305.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 34 [2018-06-22 15:01:46,673 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:01:46,673 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:01:46,673 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:01:46,678 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 15:01:46,797 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 15:01:46,797 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:01:46,802 INFO ]: Computing forward predicates... [2018-06-22 15:01:46,971 WARN ]: Spent 127.00 ms on a formula simplification. DAG size of input: 21 DAG size of output: 12 [2018-06-22 15:01:49,879 WARN ]: Spent 2.68 s on a formula simplification. DAG size of input: 61 DAG size of output: 28 [2018-06-22 15:01:50,345 WARN ]: Spent 355.00 ms on a formula simplification. DAG size of input: 55 DAG size of output: 28 [2018-06-22 15:01:50,640 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:01:50,659 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:01:50,659 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 17 [2018-06-22 15:01:50,660 INFO ]: Interpolant automaton has 17 states [2018-06-22 15:01:50,660 INFO ]: Constructing interpolant automaton starting with 17 interpolants. [2018-06-22 15:01:50,660 INFO ]: CoverageRelationStatistics Valid=49, Invalid=223, Unknown=0, NotChecked=0, Total=272 [2018-06-22 15:01:50,660 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 17 states. [2018-06-22 15:01:50,969 WARN ]: Spent 262.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 44 [2018-06-22 15:01:51,247 WARN ]: Spent 162.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 35 [2018-06-22 15:01:51,413 WARN ]: Spent 148.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 33 [2018-06-22 15:01:51,674 WARN ]: Spent 237.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 36 [2018-06-22 15:01:51,713 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:01:51,713 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-22 15:01:51,717 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 15:01:51,717 INFO ]: Start accepts. Automaton has 17 states. Word has length 25 [2018-06-22 15:01:51,717 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:01:51,718 INFO ]: With dead ends: 21 [2018-06-22 15:01:51,718 INFO ]: Without dead ends: 21 [2018-06-22 15:01:51,718 INFO ]: 0 DeclaredPredicates, 42 GetRequests, 18 SyntacticMatches, 3 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 78 ImplicationChecksByTransitivity, 5.2s TimeCoverageRelationStatistics Valid=107, Invalid=399, Unknown=0, NotChecked=0, Total=506 [2018-06-22 15:01:51,718 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 15:01:51,721 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-22 15:01:51,721 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 15:01:51,722 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-22 15:01:51,722 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-22 15:01:51,722 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:01:51,722 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-22 15:01:51,722 INFO ]: Interpolant automaton has 17 states. [2018-06-22 15:01:51,722 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-22 15:01:51,723 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 15:01:51,723 INFO ]: Found error trace [2018-06-22 15:01:51,723 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:01:51,723 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:01:51,723 INFO ]: Analyzing trace with hash 853117551, now seen corresponding path program 5 times [2018-06-22 15:01:51,723 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:01:51,723 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:01:51,724 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:01:51,724 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:01:51,724 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:01:51,833 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:01:52,605 WARN ]: Spent 521.00 ms on a formula simplification. DAG size of input: 17 DAG size of output: 15 [2018-06-22 15:01:53,113 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:01:53,113 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:01:53,113 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:01:53,129 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 15:01:53,274 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-22 15:01:53,274 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:01:53,282 INFO ]: Computing forward predicates... [2018-06-22 15:01:53,963 WARN ]: Spent 454.00 ms on a formula simplification. DAG size of input: 84 DAG size of output: 38 [2018-06-22 15:01:54,275 WARN ]: Spent 277.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 32 [2018-06-22 15:01:54,481 WARN ]: Spent 171.00 ms on a formula simplification. DAG size of input: 55 DAG size of output: 28 [2018-06-22 15:01:54,953 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:01:54,973 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:01:54,973 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 20 [2018-06-22 15:01:54,973 INFO ]: Interpolant automaton has 20 states [2018-06-22 15:01:54,974 INFO ]: Constructing interpolant automaton starting with 20 interpolants. [2018-06-22 15:01:54,974 INFO ]: CoverageRelationStatistics Valid=55, Invalid=325, Unknown=0, NotChecked=0, Total=380 [2018-06-22 15:01:54,975 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 20 states. [2018-06-22 15:01:55,485 WARN ]: Spent 448.00 ms on a formula simplification. DAG size of input: 65 DAG size of output: 51 [2018-06-22 15:01:55,699 WARN ]: Spent 189.00 ms on a formula simplification. DAG size of input: 59 DAG size of output: 28 [2018-06-22 15:01:56,116 WARN ]: Spent 391.00 ms on a formula simplification. DAG size of input: 63 DAG size of output: 33 [2018-06-22 15:01:56,510 WARN ]: Spent 369.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 35 [2018-06-22 15:01:56,852 WARN ]: Spent 296.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 35 [2018-06-22 15:01:57,082 WARN ]: Spent 208.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 32 [2018-06-22 15:01:57,113 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:01:57,113 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-22 15:01:57,116 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 15:01:57,116 INFO ]: Start accepts. Automaton has 20 states. Word has length 29 [2018-06-22 15:01:57,116 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:01:57,117 INFO ]: With dead ends: 23 [2018-06-22 15:01:57,117 INFO ]: Without dead ends: 23 [2018-06-22 15:01:57,117 INFO ]: 0 DeclaredPredicates, 49 GetRequests, 21 SyntacticMatches, 3 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 107 ImplicationChecksByTransitivity, 4.3s TimeCoverageRelationStatistics Valid=135, Invalid=567, Unknown=0, NotChecked=0, Total=702 [2018-06-22 15:01:57,118 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-22 15:01:57,125 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-22 15:01:57,125 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-22 15:01:57,126 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-22 15:01:57,126 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-22 15:01:57,126 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:01:57,126 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-22 15:01:57,126 INFO ]: Interpolant automaton has 20 states. [2018-06-22 15:01:57,126 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-22 15:01:57,127 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-22 15:01:57,127 INFO ]: Found error trace [2018-06-22 15:01:57,127 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:01:57,127 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:01:57,127 INFO ]: Analyzing trace with hash -1661294575, now seen corresponding path program 6 times [2018-06-22 15:01:57,127 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:01:57,127 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:01:57,130 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:01:57,130 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:01:57,130 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:01:57,260 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:01:57,833 WARN ]: Spent 328.00 ms on a formula simplification. DAG size of input: 19 DAG size of output: 16 [2018-06-22 15:01:58,065 WARN ]: Spent 129.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 30 [2018-06-22 15:01:58,201 WARN ]: Spent 122.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 32 [2018-06-22 15:01:58,560 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:01:58,560 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:01:58,560 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:01:58,566 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 15:01:58,734 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-22 15:01:58,734 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:01:58,743 INFO ]: Computing forward predicates... [2018-06-22 15:01:59,525 WARN ]: Spent 642.00 ms on a formula simplification. DAG size of input: 142 DAG size of output: 35 [2018-06-22 15:01:59,776 WARN ]: Spent 150.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 28 [2018-06-22 15:02:00,047 WARN ]: Spent 227.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 32 [2018-06-22 15:02:00,737 WARN ]: Spent 579.00 ms on a formula simplification. DAG size of input: 96 DAG size of output: 49 [2018-06-22 15:02:00,915 WARN ]: Spent 144.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 28 [2018-06-22 15:02:01,786 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 15:02:01,797 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 15:02:01,803 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 15:02:01,809 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 15:02:01,929 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:02:01,957 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:02:01,957 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 25 [2018-06-22 15:02:01,958 INFO ]: Interpolant automaton has 25 states [2018-06-22 15:02:01,958 INFO ]: Constructing interpolant automaton starting with 25 interpolants. [2018-06-22 15:02:01,958 INFO ]: CoverageRelationStatistics Valid=74, Invalid=526, Unknown=0, NotChecked=0, Total=600 [2018-06-22 15:02:01,958 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 25 states. [2018-06-22 15:02:02,533 WARN ]: Spent 529.00 ms on a formula simplification. DAG size of input: 87 DAG size of output: 66 [2018-06-22 15:02:03,057 WARN ]: Spent 420.00 ms on a formula simplification. DAG size of input: 85 DAG size of output: 30 [2018-06-22 15:02:03,636 WARN ]: Spent 551.00 ms on a formula simplification. DAG size of input: 89 DAG size of output: 40 [2018-06-22 15:02:04,280 WARN ]: Spent 613.00 ms on a formula simplification. DAG size of input: 89 DAG size of output: 36 [2018-06-22 15:02:04,842 WARN ]: Spent 533.00 ms on a formula simplification. DAG size of input: 90 DAG size of output: 37 [2018-06-22 15:02:05,307 WARN ]: Spent 432.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 34 [2018-06-22 15:02:05,720 WARN ]: Spent 386.00 ms on a formula simplification. DAG size of input: 89 DAG size of output: 36 [2018-06-22 15:02:05,757 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:02:05,757 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-22 15:02:05,757 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 15:02:05,757 INFO ]: Start accepts. Automaton has 25 states. Word has length 33 [2018-06-22 15:02:05,758 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:02:05,758 INFO ]: With dead ends: 25 [2018-06-22 15:02:05,758 INFO ]: Without dead ends: 25 [2018-06-22 15:02:05,759 INFO ]: 0 DeclaredPredicates, 55 GetRequests, 22 SyntacticMatches, 3 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 145 ImplicationChecksByTransitivity, 6.9s TimeCoverageRelationStatistics Valid=191, Invalid=801, Unknown=0, NotChecked=0, Total=992 [2018-06-22 15:02:05,759 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-22 15:02:05,762 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-22 15:02:05,762 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-22 15:02:05,762 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-22 15:02:05,762 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-22 15:02:05,763 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:02:05,763 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-22 15:02:05,763 INFO ]: Interpolant automaton has 25 states. [2018-06-22 15:02:05,763 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-22 15:02:05,763 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-22 15:02:05,763 INFO ]: Found error trace [2018-06-22 15:02:05,764 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:02:05,764 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:02:05,764 INFO ]: Analyzing trace with hash -1494134477, now seen corresponding path program 7 times [2018-06-22 15:02:05,764 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:02:05,764 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:02:05,764 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:02:05,764 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:02:05,764 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:02:05,922 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:02:06,899 WARN ]: Spent 703.00 ms on a formula simplification. DAG size of input: 17 DAG size of output: 15 [2018-06-22 15:02:07,148 WARN ]: Spent 105.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 29 [2018-06-22 15:02:07,311 WARN ]: Spent 153.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 34 [2018-06-22 15:02:07,666 WARN ]: Spent 222.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 39 [2018-06-22 15:02:07,947 WARN ]: Spent 110.00 ms on a formula simplification. DAG size of input: 31 DAG size of output: 17 [2018-06-22 15:02:08,177 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:02:08,178 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:02:08,178 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) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:02:08,184 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:02:08,354 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:02:08,364 INFO ]: Computing forward predicates... [2018-06-22 15:02:09,232 WARN ]: Spent 560.00 ms on a formula simplification. DAG size of input: 110 DAG size of output: 42 [2018-06-22 15:02:09,415 WARN ]: Spent 123.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 33 [2018-06-22 15:02:09,602 WARN ]: Spent 144.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 28 [2018-06-22 15:02:09,876 WARN ]: Spent 224.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 32 [2018-06-22 15:02:10,103 WARN ]: Spent 167.00 ms on a formula simplification. DAG size of input: 55 DAG size of output: 28 [2018-06-22 15:02:10,249 WARN ]: Spent 113.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 28 [2018-06-22 15:02:10,856 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:02:10,877 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:02:10,877 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 27 [2018-06-22 15:02:10,877 INFO ]: Interpolant automaton has 27 states [2018-06-22 15:02:10,877 INFO ]: Constructing interpolant automaton starting with 27 interpolants. [2018-06-22 15:02:10,878 INFO ]: CoverageRelationStatistics Valid=78, Invalid=624, Unknown=0, NotChecked=0, Total=702 [2018-06-22 15:02:10,878 INFO ]: Start difference. First operand 25 states and 26 transitions. Second operand 27 states. [2018-06-22 15:02:11,501 WARN ]: Spent 559.00 ms on a formula simplification. DAG size of input: 81 DAG size of output: 64 [2018-06-22 15:02:11,847 WARN ]: Spent 244.00 ms on a formula simplification. DAG size of input: 75 DAG size of output: 28 [2018-06-22 15:02:12,268 WARN ]: Spent 323.00 ms on a formula simplification. DAG size of input: 79 DAG size of output: 42 [2018-06-22 15:02:12,757 WARN ]: Spent 373.00 ms on a formula simplification. DAG size of input: 79 DAG size of output: 49 [2018-06-22 15:02:13,061 WARN ]: Spent 276.00 ms on a formula simplification. DAG size of input: 80 DAG size of output: 36 [2018-06-22 15:02:13,467 WARN ]: Spent 376.00 ms on a formula simplification. DAG size of input: 79 DAG size of output: 46 [2018-06-22 15:02:13,873 WARN ]: Spent 369.00 ms on a formula simplification. DAG size of input: 79 DAG size of output: 44 [2018-06-22 15:02:14,261 WARN ]: Spent 359.00 ms on a formula simplification. DAG size of input: 80 DAG size of output: 45 [2018-06-22 15:02:14,316 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:02:14,316 INFO ]: Finished difference Result 27 states and 28 transitions. [2018-06-22 15:02:14,317 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-22 15:02:14,317 INFO ]: Start accepts. Automaton has 27 states. Word has length 37 [2018-06-22 15:02:14,317 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:02:14,318 INFO ]: With dead ends: 27 [2018-06-22 15:02:14,318 INFO ]: Without dead ends: 27 [2018-06-22 15:02:14,318 INFO ]: 0 DeclaredPredicates, 62 GetRequests, 26 SyntacticMatches, 3 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 173 ImplicationChecksByTransitivity, 6.9s TimeCoverageRelationStatistics Valid=220, Invalid=970, Unknown=0, NotChecked=0, Total=1190 [2018-06-22 15:02:14,319 INFO ]: Start minimizeSevpa. Operand 27 states. [2018-06-22 15:02:14,322 INFO ]: Finished minimizeSevpa. Reduced states from 27 to 27. [2018-06-22 15:02:14,322 INFO ]: Start removeUnreachable. Operand 27 states. [2018-06-22 15:02:14,323 INFO ]: Finished removeUnreachable. Reduced from 27 states to 27 states and 28 transitions. [2018-06-22 15:02:14,324 INFO ]: Start accepts. Automaton has 27 states and 28 transitions. Word has length 37 [2018-06-22 15:02:14,324 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:02:14,324 INFO ]: Abstraction has 27 states and 28 transitions. [2018-06-22 15:02:14,324 INFO ]: Interpolant automaton has 27 states. [2018-06-22 15:02:14,324 INFO ]: Start isEmpty. Operand 27 states and 28 transitions. [2018-06-22 15:02:14,325 INFO ]: Finished isEmpty. Found accepting run of length 42 [2018-06-22 15:02:14,325 INFO ]: Found error trace [2018-06-22 15:02:14,325 INFO ]: trace histogram [9, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:02:14,325 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:02:14,325 INFO ]: Analyzing trace with hash 1618126293, now seen corresponding path program 8 times [2018-06-22 15:02:14,325 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:02:14,325 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:02:14,326 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:02:14,326 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:02:14,326 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:02:14,601 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:02:15,116 WARN ]: Spent 164.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 45 [2018-06-22 15:02:15,309 WARN ]: Spent 183.00 ms on a formula simplification. DAG size of input: 58 DAG size of output: 45 [2018-06-22 15:02:15,467 WARN ]: Spent 118.00 ms on a formula simplification. DAG size of input: 51 DAG size of output: 41 [2018-06-22 15:02:15,597 WARN ]: Spent 115.00 ms on a formula simplification. DAG size of input: 50 DAG size of output: 42 [2018-06-22 15:02:16,268 WARN ]: Spent 111.00 ms on a formula simplification. DAG size of input: 33 DAG size of output: 28 [2018-06-22 15:02:16,336 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:02:16,336 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:02:16,337 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:02:16,343 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 15:02:16,550 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 15:02:16,550 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:02:16,561 INFO ]: Computing forward predicates... [2018-06-22 15:02:17,200 WARN ]: Spent 502.00 ms on a formula simplification. DAG size of input: 79 DAG size of output: 59 [2018-06-22 15:02:17,640 WARN ]: Spent 329.00 ms on a formula simplification. DAG size of input: 65 DAG size of output: 44 [2018-06-22 15:02:18,141 WARN ]: Spent 454.00 ms on a formula simplification. DAG size of input: 61 DAG size of output: 44 [2018-06-22 15:02:18,562 WARN ]: Spent 330.00 ms on a formula simplification. DAG size of input: 57 DAG size of output: 36 [2018-06-22 15:02:19,059 WARN ]: Spent 437.00 ms on a formula simplification. DAG size of input: 83 DAG size of output: 40 [2018-06-22 15:02:19,296 WARN ]: Spent 190.00 ms on a formula simplification. DAG size of input: 55 DAG size of output: 28 [2018-06-22 15:02:19,459 WARN ]: Spent 127.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 28 [2018-06-22 15:02:22,783 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:02:22,803 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:02:22,803 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 20] total 34 [2018-06-22 15:02:22,804 INFO ]: Interpolant automaton has 34 states [2018-06-22 15:02:22,804 INFO ]: Constructing interpolant automaton starting with 34 interpolants. [2018-06-22 15:02:22,804 INFO ]: CoverageRelationStatistics Valid=103, Invalid=1019, Unknown=0, NotChecked=0, Total=1122 [2018-06-22 15:02:22,804 INFO ]: Start difference. First operand 27 states and 28 transitions. Second operand 34 states. [2018-06-22 15:02:24,749 WARN ]: Spent 1.87 s on a formula simplification. DAG size of input: 151 DAG size of output: 116 [2018-06-22 15:02:25,283 WARN ]: Spent 446.00 ms on a formula simplification. DAG size of input: 151 DAG size of output: 39 [2018-06-22 15:02:26,143 WARN ]: Spent 794.00 ms on a formula simplification. DAG size of input: 154 DAG size of output: 78 [2018-06-22 15:02:27,163 WARN ]: Spent 957.00 ms on a formula simplification. DAG size of input: 152 DAG size of output: 79 [2018-06-22 15:02:27,925 WARN ]: Spent 692.00 ms on a formula simplification. DAG size of input: 154 DAG size of output: 84 [2018-06-22 15:02:28,640 WARN ]: Spent 662.00 ms on a formula simplification. DAG size of input: 154 DAG size of output: 81 [2018-06-22 15:02:29,341 WARN ]: Spent 635.00 ms on a formula simplification. DAG size of input: 154 DAG size of output: 80 [2018-06-22 15:02:30,017 WARN ]: Spent 626.00 ms on a formula simplification. DAG size of input: 154 DAG size of output: 76 [2018-06-22 15:02:30,735 WARN ]: Spent 668.00 ms on a formula simplification. DAG size of input: 153 DAG size of output: 75 [2018-06-22 15:02:30,792 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:02:30,792 INFO ]: Finished difference Result 29 states and 30 transitions. [2018-06-22 15:02:30,793 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-22 15:02:30,793 INFO ]: Start accepts. Automaton has 34 states. Word has length 41 [2018-06-22 15:02:30,793 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:02:30,793 INFO ]: With dead ends: 29 [2018-06-22 15:02:30,793 INFO ]: Without dead ends: 29 [2018-06-22 15:02:30,794 INFO ]: 0 DeclaredPredicates, 69 GetRequests, 27 SyntacticMatches, 1 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 229 ImplicationChecksByTransitivity, 12.4s TimeCoverageRelationStatistics Valid=293, Invalid=1513, Unknown=0, NotChecked=0, Total=1806 [2018-06-22 15:02:30,794 INFO ]: Start minimizeSevpa. Operand 29 states. [2018-06-22 15:02:30,798 INFO ]: Finished minimizeSevpa. Reduced states from 29 to 29. [2018-06-22 15:02:30,798 INFO ]: Start removeUnreachable. Operand 29 states. [2018-06-22 15:02:30,799 INFO ]: Finished removeUnreachable. Reduced from 29 states to 29 states and 30 transitions. [2018-06-22 15:02:30,799 INFO ]: Start accepts. Automaton has 29 states and 30 transitions. Word has length 41 [2018-06-22 15:02:30,799 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:02:30,799 INFO ]: Abstraction has 29 states and 30 transitions. [2018-06-22 15:02:30,799 INFO ]: Interpolant automaton has 34 states. [2018-06-22 15:02:30,799 INFO ]: Start isEmpty. Operand 29 states and 30 transitions. [2018-06-22 15:02:30,801 INFO ]: Finished isEmpty. Found accepting run of length 46 [2018-06-22 15:02:30,801 INFO ]: Found error trace [2018-06-22 15:02:30,801 INFO ]: trace histogram [10, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:02:30,801 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:02:30,801 INFO ]: Analyzing trace with hash 996918775, now seen corresponding path program 9 times [2018-06-22 15:02:30,801 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:02:30,801 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:02:30,802 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:02:30,802 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:02:30,802 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:02:31,025 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:02:31,963 WARN ]: Spent 630.00 ms on a formula simplification. DAG size of input: 23 DAG size of output: 20 [2018-06-22 15:02:32,106 WARN ]: Spent 136.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 49 [2018-06-22 15:02:32,219 WARN ]: Spent 105.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 47 [2018-06-22 15:02:32,339 WARN ]: Spent 109.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 43 [2018-06-22 15:02:32,571 WARN ]: Spent 111.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 42 [2018-06-22 15:02:32,697 WARN ]: Spent 110.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 37 [2018-06-22 15:02:33,342 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:02:33,343 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:02:33,343 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:02:33,348 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 15:02:33,588 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2018-06-22 15:02:33,589 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:02:33,600 INFO ]: Computing forward predicates... Received shutdown request... [2018-06-22 15:02:35,068 WARN ]: Removed 4 from assertion stack [2018-06-22 15:02:35,068 INFO ]: Timeout while computing interpolants [2018-06-22 15:02:35,269 WARN ]: Destroyed unattended storables created during the last iteration: 11 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:02:35,269 WARN ]: Verification canceled [2018-06-22 15:02:35,272 WARN ]: Timeout [2018-06-22 15:02:35,272 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 03:02:35 BoogieIcfgContainer [2018-06-22 15:02:35,272 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 15:02:35,273 INFO ]: Toolchain (without parser) took 59654.03 ms. Allocated memory was 306.2 MB in the beginning and 999.8 MB in the end (delta: 693.6 MB). Free memory was 238.7 MB in the beginning and 398.4 MB in the end (delta: -159.7 MB). Peak memory consumption was 533.9 MB. Max. memory is 3.6 GB. [2018-06-22 15:02:35,274 INFO ]: SmtParser took 0.09 ms. Allocated memory is still 306.2 MB. Free memory is still 271.7 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 15:02:35,274 INFO ]: ChcToBoogie took 54.47 ms. Allocated memory is still 306.2 MB. Free memory was 237.7 MB in the beginning and 235.7 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:02:35,274 INFO ]: Boogie Preprocessor took 57.72 ms. Allocated memory is still 306.2 MB. Free memory was 235.7 MB in the beginning and 233.7 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:02:35,275 INFO ]: RCFGBuilder took 382.46 ms. Allocated memory is still 306.2 MB. Free memory was 233.7 MB in the beginning and 211.2 MB in the end (delta: 22.5 MB). Peak memory consumption was 22.5 MB. Max. memory is 3.6 GB. [2018-06-22 15:02:35,275 INFO ]: TraceAbstraction took 59148.78 ms. Allocated memory was 306.2 MB in the beginning and 999.8 MB in the end (delta: 693.6 MB). Free memory was 211.2 MB in the beginning and 398.4 MB in the end (delta: -187.2 MB). Peak memory consumption was 506.4 MB. Max. memory is 3.6 GB. [2018-06-22 15:02:35,279 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.09 ms. Allocated memory is still 306.2 MB. Free memory is still 271.7 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 54.47 ms. Allocated memory is still 306.2 MB. Free memory was 237.7 MB in the beginning and 235.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 57.72 ms. Allocated memory is still 306.2 MB. Free memory was 235.7 MB in the beginning and 233.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 382.46 ms. Allocated memory is still 306.2 MB. Free memory was 233.7 MB in the beginning and 211.2 MB in the end (delta: 22.5 MB). Peak memory consumption was 22.5 MB. Max. memory is 3.6 GB. * TraceAbstraction took 59148.78 ms. Allocated memory was 306.2 MB in the beginning and 999.8 MB in the end (delta: 693.6 MB). Free memory was 211.2 MB in the beginning and 398.4 MB in the end (delta: -187.2 MB). Peak memory consumption was 506.4 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 analyzing trace of length 46 with TraceHistMax 10, while TraceCheckSpWp was constructing forward predicates, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 831. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 59.0s OverallTime, 10 OverallIterations, 10 TraceHistogramMax, 20.9s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 127 SDtfs, 392 SDslu, 820 SDs, 0 SdLazy, 767 SolverSat, 473 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 1.3s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 364 GetRequests, 157 SyntacticMatches, 16 SemanticMatches, 191 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 809 ImplicationChecksByTransitivity, 42.9s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=29occurred in iteration=9, 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, 9 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.1s SsaConstructionTime, 2.0s SatisfiabilityAnalysisTime, 30.9s InterpolantComputationTime, 441 NumberOfCodeBlocks, 441 NumberOfCodeBlocksAsserted, 33 NumberOfCheckSat, 424 ConstructedInterpolants, 0 QuantifiedInterpolants, 556892 SizeOfPredicates, 746 NumberOfNonLiveVariables, 5280 ConjunctsInSsa, 511 ConjunctsInUnsatCore, 17 InterpolantComputations, 1 PerfectInterpolantSequences, 240/888 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/efm.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_15-02-35-289.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/efm.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_15-02-35-289.csv Completed graceful shutdown